Le graphe ci-dessous indique les différentes liaisons entre plusieurs lieux. Le long de chaque arête figure la distance en kilomètres séparant les différents lieux.
En précisant la méthode utilisée, déterminer le plus court chemin possible pour aller de A à L.
Pour déterminer le plus court chemin possible pour aller de A à L, on utilise l'algorithme de Dijkstra.
| A | B | C | D | E | F | G | H | I | J | K | L | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | A (0) |
| 10 (A) | ∞ | ∞ | 2 (A) | 8 (A) | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | E (2) | |
| 10 (A) | ∞ | ∞ | 8 (A) | ∞ | ∞ | 3 (E) | 6 (E) | ∞ | ∞ | I (3) | ||
| 10 (A) | ∞ | ∞ | 8 (A) | ∞ | ∞ | 5 (I) | ∞ | ∞ | J (5) | |||
| 10 (A) | ∞ | ∞ | 7 (J) | 11 (J) | ∞ | ∞ | ∞ | F (7) | ||||
| 10 (A) | ∞ | ∞ | 10 (F) | ∞ | ∞ | ∞ | B (10) | |||||
| 12 (B) | ∞ | 10 (F) | ∞ | ∞ | ∞ | G (10) | ||||||
| 11 (G) | 13 (G) | 20 (G) | 18 (G) | 19 (G) | C (11) | |||||||
| 13 (G) | 20 (G) | 18 (G) | 19 (G) | D (13) | ||||||||
| 15 (D) | 18 (G) | 19 (G) | H (15) | |||||||||
| 18 (G) | 18 (H) | K (18) | ||||||||||
| 18 (H) | L (18) |
Tous les sommets étant marqués, pour lire la chaîne la plus courte, on part de L et on "remonte" la chaîne en suivant les sommets de provenance..
Le plus court chemin possible pour aller de A à L est : A-E-I-J-F-G-D-H-L avec une distance parcourue de 18 km.
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.