Différences

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

--- les_exposes:plus_court_chemin [29/09/2016 08:46]
paquier créée
+++ les_exposes:plus_court_chemin [30/10/2016 19:04]
paquier
@@ Ligne 1: / Ligne 1: @@
-Chloé Paquier
+__**Comment un GPS peut trouver le plus court chemin parmi plusieurs?
+**__
+L'algorithme de Dijkstra permet de déterminer le plus court chemin pour se rendre d'un endroit a un autre par exemple d'une ville a une autre sachant le reseau routier de la région.
+{{:les_exposes:dijkstra_animation.gif?200|}}  <-- execution de l'algorithme.
+L'algorithme porte le nom de son inventeur, l'informaticien néerlandais **Edsger Dijkstra**, et a été publié en 19591.
+{{ :les_exposes:edsger.jpg?200 |}}
+Plus précisément,L'algorithme de Dijkstra calcule des plus courts chemins à partir d'une source dans un graphe orienté pondéré par des réels positifs.
+On peut aussi l'utiliser pour calculer un plus court chemin entre une source et un sommet d'arrivée
+**__
+Exemple pour mieux comprendre:
+__
+**
+L'algorithme prend en entrée un graphe orienté pondéré par des réels positifs et un sommet source.
+{{:les_exposes:545px-dijkstrabis01.svg.png?200|}}
+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.
+Au cours de chaque itération, on choisit en dehors du sous-graphe un sommet de distance minimale et on l'ajoute au sous-graphe. Ensuite, on met à jour les distances des sommets voisins de celui ajouté. La mise à jour s'opère comme suit : la nouvelle distance du sommet voisin est le minimum entre la distance existante et celle obtenue en ajoutant le poids de l'arc entre sommet voisin et sommet ajouté à la distance du sommet ajouté.
+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