La recherche du meilleur itinéraire que ce soit en distance, en temps ou en coût d'un point à un autre peut être modélisée par la recherche du plus court chemin dans un graphe.
Dans ce paragraphe, on s'intéresse à la recherche d'un plus court chemin dans un graphe entre deux sommets donnés.
On appelle graphe pondéré, un graphe (orienté ou non) dont les arêtes ont été affectées d'un nombre appelé poids (ou coût).
Par analogie avec la matrice d'adjacence, on peut définir la matrice des poids du graphe, dont les coefficients correspondent aux poids des arêtes (ou des arcs dans le cas d'un graphe orienté) : On utilise le symbole ∞ pour indiquer qu'il n'y a pas d'arêtes entre deux sommets.
exemple
Les sommets du graphe étant rangés dans l'ordre alphabétique la matrice des poids est : |
Soit un chemin (ou une chaîne) dans un graphe pondéré G du sommet x vers le sommet y. La longueur de ce chemin est égale à la somme des poids de chacun arcs ( ou de chacune des arêtes) qui le constituent.
remarque
Cette définition généralise la définition de la longueur d'une chaîne dans un graphe non pondéré, il suffit d'attribuer un poids égal à 1 à chaque arête du graphe.
Dans le graphe précédent, la longueur du chemin A-E-F-G est .
Si on souhaite déterminer le plus court chemin entre deux sommets d'un graphe, on peut essayer d'énumérer tous les chemins possibles entre ces deux sommets et calculer leurs longueurs. Mais avec un graphe de taille importante, ceci risque de devenir rapidement impossible.
Pour résoudre ce problème, on fait appel à des algorithmes.
En terminale ES, on n'étudie que le cas particulier où les poids de tous les arcs sont des réels positifs.
E. W. Dijkstra (1930-2002) 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.
L'algorithme dû à Dijkstra est basé sur le principe suivant :
Si le plus court chemin reliant le sommet de départ à un autre sommet S passe par les sommets , , …, alors, les différentes étapes sont aussi les plus courts chemins reliant A aux différents sommets , , …, .
On construit de proche en proche le chemin cherché en choisissant à chaque itération de l'algorithme, un sommet du graphe parmi ceux qui n'ont pas encore été traités, tel que la longueur connue provisoirement du plus court chemin allant de à soit la plus courte possible.
L'algorithme comporte une phase d'initialisation. À chaque sommet on attribue un poids qui vaut 0 pour le sommet de départ et infini pour les autres sommets.
Soit G un graphe connexe dont les arêtes sont pondérées par des nombres positifs.
notations :
initialisation :
Pour ChaqueFaire | On attribue un poids ∞ à chacun des sommetsx |
Le poids du sommet est nul | |
La liste des sommets restant à traiter est initialisée à S | |
La liste des sommets déjà traités vide |
traitement :
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. Quel est l'itinéraire le plus court qui relie A à H ?
Vous pouvez observer le déroulement de l'algorithme de Dijkstra pas à pas en cliquant sur le bouton.
Pour faciliter la recherche du plus court chemin il est commode de présenter les résultats dans un tableau
A | B | C | D | E | F | G | H | Sommets sélectionnés | Commentaires |
0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | A (0) | On affecte le poids 0 au sommet origine (A) et on attribue provisoirement un poids ∞ aux autres sommets. Le sommet A de poids 0 est selectionné. |
7 (A) | ∞ | ∞ | 14 (A) | ∞ | ∞ | ∞ | B (7) | Le sommet A de poids 0 ayant été selectionné, on marque provisoirement les sommets B et E adjacents à A. On selectionne le sommet B de poids minimal. Le prédécesseur de B est A. | |
15 (B) | ∞ | 14 (A) | ∞ | ∞ | ∞ | E (14) | B de poids 7 ayant été selectionné, on marque provisoirement le sommet C adjacent à B. On selectionne le sommet E de poids minimal. Le prédécesseur de E est A. | ||
15 (B) | ∞ | 33 (E) | ∞ | ∞ | C (15) | E de poids 14 ayant été selectionné, on marque provisoirement le sommet F adjacent à E. On selectionne le sommet C de poids minimal. Le prédécesseur de C est B. | |||
21 (C) | 33 (E) | ∞ | ∞ | D (21) | C de poids 15 ayant été selectionné, on marque provisoirement le sommet D adjacent à C. On selectionne le sommet D de poids minimal. Le prédécesseur de D est C. | ||||
32 (D) | ∞ | ∞ | F (32) | D de poids 21 ayant été selectionné, on marque provisoirement le sommet F adjacent à D. On selectionne le sommet F de poids minimal. Le prédécesseur de F est D. | |||||
36 (F) | 45 (F) | G (36) | F de poids 32 ayant été selectionné, on marque provisoirement les sommets G et E adjacent à F. On selectionne le sommet G de poids minimal. Le prédécesseur de G est F. | ||||||
44 (G) | H (44) | G de poids 36 ayant été selectionné, on marque provisoirement le sommet H . On selectionne le sommet H de poids minimal. Le prédécesseur de H est G. |
Le sommet final H étant marqué, pour lire la chaîne de poids minimal, on part de H et on remonte la chaîne en suivant les prédécesseurs. .
Le trajet le plus court pour aller de A à H est A - B - C - D - F - G - H, la distance parcourue est 44 km.
Dans le graphe pondéré ci-dessous, les poids des arêtes sont déterminés de manère aléatoire. Un papier un crayon, et vérifiez vos résultats ...
Vous pouvez vérifier le déroulement de l'algorithme de Dijkstra pas à pas en cliquant sur le bouton.
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.