Différences

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

--- les_exposes:plus_court_chemin [30/10/2016 18:37]
paquier
+++ les_exposes:plus_court_chemin [30/10/2016 19:04]
paquier
@@ Ligne 23: / Ligne 23: @@
 Il s'agit de construire progressivement un sous-graphe dans lequel sont classés les différents sommets par ordre croissant de leur distance minimale au sommet de départ. La distance correspond à la somme des poids des arcs empruntées.
 Au départ, on considère que les distances de chaque sommet au sommet de départ sont infinies sauf pour le sommet de départ pour lequel la distance est de 0. Le sous-graphe de départ est l'ensemble vide.
@@ Ligne 29: / Ligne 30: @@
 On continue ainsi jusqu'à épuisement des sommets (ou jusqu'à sélection du sommet d'arrivée).
+**__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-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.
+{{:les_exposes:545px-dijkstrabis03.svg.png?200|}}
+<-- : on choisit F. On met à jour le voisin I (415).
+{{: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