Définition 1
Graphes orientés : chaque arête possède
un sens, soit du sommet A au sommet B, soit l'inverse.
Définition
2
Graphes étiquetés : chaque arête possède
un nom.
Définition 3
Graphes pondérés : chaque arête possède
un poids, c'est à dire un nombre correspondant aux données du
problème représenté par le graphe.
Définition
4
Dans un graphe pondéré on peut calculer le poids
d'une chaîne en ajoutant le poids de toutes les arêtes qui la composent.
Définition
5
On peut alors déterminer la chaîne de plus faible
poids d'un sommet à un autre. On parle aussi de chemin le plus court.
Pour cela on utilise l'algorithme de Dijkstra.
Le poids de l'arête 2 - 6 est 4.
Le poids de la chaîne 3 - 4 - 5 - 8 est 3 + 1 + 4 = 8