Différences

Ci-dessous, les différences entre deux révisions de la page.

--- les_exposes:plus_court_chemin [30/10/2016 18:50]
paquier
+++ les_exposes:plus_court_chemin [30/10/2016 19:04]
paquier
@@ Ligne 33: / Ligne 33: @@
 **__Exemple en image__**
-{{: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.
+{{:les_exposes:545px-dijkstrabis01.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 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-dijkstrabis03.svg.png?200|}} <-- : on choisit F. On met à jour le voisin I (415).
+{{:les_exposes:545px-dijkstrabis02.svg.png?200|}}
-{{:les_exposes:545px-dijkstrabis04.svg.png?200|}} <--  on choisit E. On met à jour le voisin J (675).
-{{:les_exposes:545px-dijkstrabis05.svg.png?200|}} <-- la distance la plus courte en dehors du sous-graphe est maintenant celle de la ville C. On choisit donc C. On met à jour la ville G (403) et la ville H (320).
+<-- 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-dijkstrabis06.svg.png?200|}} <--  la distance la plus courte en dehors du sous-graphe est maintenant celle de la ville H (320). On choisit donc H. On met à jour la ville D (503) et la ville J (487< 675).
-{{:les_exposes:545px-dijkstrabis07.svg.png?200|}} <-- la distance la plus courte suivante est celle de la ville G. On choisit G. La mise à jour ne change aucune autre distance.
+{{:les_exposes:545px-dijkstrabis03.svg.png?200|}}
-{{:les_exposes:545px-dijkstrabis08.svg.png?200|}}<--  la distance la plus courte suivante est celle de la ville I. La distance de la ville voisine J n'est pas modifiée car la distance existante est inférieure à celle que l'on obtiendrait en passant par I (415 + 84 > 487).
+<-- : on choisit F. On met à jour le voisin I (415).
-{{:les_exposes:545px-dijkstrabis09.svg.png?200|}} <-- 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.
+{{:les_exposes:545px-dijkstrabis04.svg.png?200|}}
+<--  on choisit E. On met à jour le voisin J (675).
+{{:les_exposes:545px-dijkstrabis05.svg.png?200|}}
+<-- la distance la plus courte en dehors du sous-graphe est maintenant celle de la ville C. On choisit donc C. On met à jour la ville G (403) et la ville H (320).
+{{:les_exposes:545px-dijkstrabis06.svg.png?200|}}
+ <-- la distance la plus courte en dehors du    sous-graphe est maintenant celle de la ville H (320). On choisit donc H. On met à jour la ville D (503) et la ville J (487< 675).
+{{:les_exposes:545px-dijkstrabis07.svg.png?200|}}
+<-- la distance la plus courte suivante est celle de la ville G. On choisit G. La mise à jour ne change aucune autre distance.
+{{:les_exposes:545px-dijkstrabis08.svg.png?200|}}
+<--  la distance la plus courte suivante est celle de la ville I. La distance de la ville voisine J n'est pas modifiée car la distance existante est inférieure à celle que l'on obtiendrait en passant par I (415 + 84 > 487).
+{{:les_exposes:545px-dijkstrabis09.svg.png?200|}}
+<-- 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.

Wiki ISN

Outils pour utilisateurs

Outils du site

Différences

Outils de la page