Définition
On appelle :
- Graphe pondéré : tout graphe dont les arêtes sont affectées des coefficients positifs.
- Poids d’une chaîne : la somme des coefficients des arêtes qui la composent.
- Parmi les chaînes qui relient deux sommets, celles qui ont le poids le plus faible sont appelées plus courtes chaînes entre ces sommets.
NB : Pour trouver une plus courte chaîne on utilise l’algorithme de DIJKSTRA.
