Outils pour utilisateurs
les_exposes:plus_court_chemin
Différences
Ci-dessous, les différences entre deux révisions de la page.
| Les deux révisions précédentes Révision précédente | Prochaine révision Les deux révisions suivantes | ||
|
les_exposes:plus_court_chemin [30/10/2016 18:55] paquier |
les_exposes:plus_court_chemin [30/10/2016 19:04] paquier |
||
|---|---|---|---|
| Ligne 34: | Ligne 34: | ||
| {{:les_exposes:545px-dijkstrabis01.svg.png?200|}} | {{:les_exposes:545px-dijkstrabis01.svg.png?200|}} | ||
| + | |||
| + | |||
| <-- on choisit la ville A. On met à jour les villes voisines de A qui sont B, C, et E. Leurs distances deviennent respectivement 85, 217, 173, tandis que les autres villes restent à une distance infinie. | <-- on choisit la ville A. On met à jour les villes voisines de A qui sont B, C, et E. Leurs distances deviennent respectivement 85, 217, 173, tandis que les autres villes restent à une distance infinie. | ||
| {{:les_exposes:545px-dijkstrabis02.svg.png?200|}} | {{:les_exposes:545px-dijkstrabis02.svg.png?200|}} | ||
| + | |||
| + | |||
| <-- on choisit la ville B. En effet, c'est la ville hors du sous-graphe qui est à la distance minimale (85). On met à jour le seul voisin (F). Sa distance devient 85+80 = 165. | <-- on choisit la ville B. En effet, c'est la ville hors du sous-graphe qui est à la distance minimale (85). On met à jour le seul voisin (F). Sa distance devient 85+80 = 165. | ||
| {{:les_exposes:545px-dijkstrabis03.svg.png?200|}} | {{:les_exposes:545px-dijkstrabis03.svg.png?200|}} | ||
| - | <-- : on choisit F. On met à jour le voisin I (415). | + | |
| + | |||
| + | <-- : on choisit F. On met à jour le voisin I (415). | ||
| {{:les_exposes:545px-dijkstrabis04.svg.png?200|}} | {{:les_exposes:545px-dijkstrabis04.svg.png?200|}} | ||
| - | <-- on choisit E. On met à jour le voisin J (675). | + | |
| + | |||
| + | <-- on choisit E. On met à jour le voisin J (675). | ||
| {{:les_exposes:545px-dijkstrabis05.svg.png?200|}} | {{:les_exposes:545px-dijkstrabis05.svg.png?200|}} | ||
| Ligne 70: | Ligne 78: | ||
| <-- la ville dont la distance est la plus courte est J (487). On choisit J et on l'ajoute au sous-graphe. On s'arrête puisque la ville d'arrivée est maintenant dans le sous-graphe. | <-- la ville dont la distance est la plus courte est J (487). On choisit J et on l'ajoute au sous-graphe. On s'arrête puisque la ville d'arrivée est maintenant dans le sous-graphe. | ||
| + | |||
| + | //On connaît ainsi le chemin le plus court menant de A à J, il passe par C et H et mesure 487 km.// | ||
| + | __** | ||
| + | Sous forme de tableau**__ | ||
| + | |||
| + | On peut aussi résumer l'exécution de l'algorithme de Dijkstra avec un tableau. Chaque étape correspond à une ligne. | ||
| + | Une ligne donne les distances courantes des sommets depuis le sommet de départ. | ||
| + | Une colonne donne l'évolution des distances d'un sommet donné depuis le sommet de départ au cours de l'algorithme. | ||
| + | La distance d'un sommet choisi (car minimale) est soulignée. Les distances mises à jour sont barrées si elles sont supérieures à des distances déjà calculées. | ||
| + | |||
| + | {{ :les_exposes:tablo.png |}} | ||
| + | |||
| + | Le tableau donne non seulement la distance minimale de la ville A à la ville J (487) mais aussi le chemin à suivre à rebours (J - H - C - A) pour aller de A à J ainsi que toutes les distances minimales de la ville A aux autres villes rangées par ordre croissant. | ||
les_exposes/plus_court_chemin.txt · Dernière modification: 02/11/2016 12:25 par paquier
Outils de la page
Sauf mention contraire, le contenu de ce wiki est placé sous les termes de la licence suivante : GNU Free Documentation License 1.3
