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 | Révision précédente Dernière révision Les deux révisions suivantes | ||
|
les_exposes:plus_court_chemin [30/10/2016 18:55] paquier |
les_exposes:plus_court_chemin [02/11/2016 12:15] paquier |
||
|---|---|---|---|
| Ligne 2: | Ligne 2: | ||
| **__ | **__ | ||
| - | 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. | + | E. W. Dijkstra a proposé en 1959 un algorithme qui permet de déterminer le plus court chemin entre deux sommets d'un graphe connexe pondéré (orienté ou non) dont le poids lié aux arêtes est positif ou nul. |
| + | |||
| + | L'algorithme de Dijkstra permet par exemple 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. | {{: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. | + | L'algorithme porte le nom de son inventeur, l'informaticien néerlandais **Edsger Dijkstra**, et a été publié en 1959. |
| {{ :les_exposes:edsger.jpg?200 |}} | {{ :les_exposes:edsger.jpg?200 |}} | ||
| Ligne 13: | Ligne 15: | ||
| 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. | 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 | On peut aussi l'utiliser pour calculer un plus court chemin entre une source et un sommet d'arrivée | ||
| + | |||
| + | L'algorithme dû à Dijkstra est basé sur le principe suivant : | ||
| + | |||
| + | Si le plus court chemin reliant E à S passe par les sommets s1 , s2 , …, sk alors, les différentes étapes sont aussi les plus courts chemins reliant E aux différents sommets s1 , s2 , …, sk. | ||
| + | |||
| + | On construit de proche en proche le chemin cherché en choisissant à chaque itération de l'algorithme, un sommet si du graphe parmi ceux qui n'ont pas encore été traités, tel que la longueur connue provisoirement du plus court chemin allant de E à si soit la plus courte possible. | ||
| **__ | **__ | ||
| Ligne 34: | Ligne 42: | ||
| {{: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 86: | ||
| <-- 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
