Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente | |||
les_exposes:plus_court_chemin [02/11/2016 12:15] paquier |
les_exposes:plus_court_chemin [02/11/2016 12:25] paquier |
||
---|---|---|---|
Ligne 14: | Ligne 14: | ||
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 | ||
+ | |||
+ | |||
+ | __**Exemple**__ | ||
+ | |||
+ | Le graphe ci-dessous représente le réseau routier d'une région qui prend en compte le sens de la circulation, chaque arc représente une route à sens unique dont le poids est la distance en kilomètre entre deux sommets. {{ :les_exposes:sans_titre.png |}} | ||
L'algorithme dû à Dijkstra est basé sur le principe suivant : | L'algorithme dû à Dijkstra est basé sur le principe suivant : | ||
Ligne 22: | Ligne 28: | ||
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. | 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. | ||
- | **__ | + | **Initialisation de l'algorithme :** |
- | 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|}} | + | Étape 1 : On affecte le poids 0 au sommet origine (E) et on attribue provisoirement un poids ∞ aux autres sommets. |
+ | **Répéter les opérations suivantes tant que le sommet de sortie (S) n'est pas affecté d'un poids définitif** | ||
- | <-- 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). | + | Étape 2 : Parmi les sommets dont le poids n'est pas définivement fixé choisir le sommet X de poids p minimal. Marquer définitivement ce sommet X affecté du poids p(X). |
- | {{:les_exposes:545px-dijkstrabis09.svg.png?200|}} | + | Étape 3 : Pour tous les sommets Y qui ne sont pas définitivement marqués, adjacents au dernier sommet fixé X : |
+ | °Calculer la somme s du poids de X et du poids de l'arête reliant X à Y. | ||
+ | ° Si la somme s est inférieure au poids provisoirement affecté au sommet Y, affecter provisoirement à Y le nouveau poids et indiquer entre parenthèses le sommet X pour se souvenir de sa provenance. | ||
- | <-- 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. | + | **Quand le sommet S est défintivement marqué** |
- | //On connaît ainsi le chemin le plus court menant de A à J, il passe par C et H et mesure 487 km.// | + | Le plus court chemin de E à S s'obtient en écrivant de gauche à droite le parcours en partant de la fin S. |
- | __** | + | {{ :les_exposes:1222.png |}} |
- | 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. | + | Pour faciliter la recherche du plus court chemin il est commode de présenter les résultats dans un tableau |
- | Une ligne donne les distances courantes des sommets depuis le sommet de départ. | + | {{:les_exposes:tableau.png|}} |
- | 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 |}} | + | Pour déterminer le trajet le plus court on remonte les sommets en partant de S : S vient de F qui vient de C qui vient de E. |
- | 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. |