Theorie des graphes

Algorithme de Dijkstra
En théorie des graphes, l’algorithme de Dijkstra (prononcer [d?jkstra]) sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer le plus court chemin pour se rendre d’une ville à une autre connaissant le réseau routier d’une région. Il s’applique à un graphe connexe dont le poids lié aux arêtes est positif ou nul.
L’algorithme porte le nomde son inventeur, l’informaticien néerlandais Edsger Dijkstra et a été publié en 1959[1].
En théorie de la complexité on démontre que cet algorithme est polynomial.
Sommaire * 1 Applications * 2 Principe sur un exemple * 2.1 Distance entre la ville A et la ville J * 2.2 Présentation sous forme de tableau * 3 Notations * 4 Principes * 5 Algorithme * 5.1 Fonctions annexes* 5.1.1 Initialisation de l’algorithme * 5.1.2 Recherche du nœud le plus proche * 5.1.3 Mise à jour des distances * 5.2 Fonction principale * 5.3 Améliorations de l’algorithme |
Applications
L’algorithme de Dijkstra trouve son utilité dans le calcul des itinéraires routiers. Le poids des arcs pouvant être la distance (pour le trajet le plus court), le tempsestimé (pour le trajet le plus rapide), le plus économique (avec la consommation de carburant et le prix des péages).
Une application des plus courantes de l’algorithme de Dijkstra est le protocole open shortest path first qui permet un routage internet très efficace des informations en cherchant le parcours le plus efficace.
Les routeurs IS-IS utilisent également l’algorithme.
Principe sur unexemple
Il s’agit de construire progressivement, à partir des données initiales, 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 arêtes empruntées.
La première étape consiste à mettre de côté le sommet de départ et à repérer la distance du sommet de départ aux autressommets du graphe. Cette distance est infinie si aucun arc ne relie le sommet au sommet de départ, elle est de n s’il existe un arc reliant ce sommet au sommet de départ et que le poids le plus faible (s’il existe plusieurs arcs) est de n.
La seconde étape consiste à repérer le sommet qui possède alors la plus courte distance au sommet de départ et à le mettre de côté. Pour tous les sommets restants,on compare alors la distance trouvée précédemment à celle que l’on obtiendrait via le sommet que l’on vient de mettre de côté et on ne conserve que la plus petite des valeurs. Puis on continue ainsi jusqu’à épuisement des sommets ou jusqu’à sélection du sommet d’arrivée.
————————————————-
Distance entre la ville A et la ville J
L’exemple suivant montre lesétapes successives dans la résolution du chemin le plus court dans un graphe. Les nœuds symbolisent des villes identifiées par une lettre et les arêtes indiquent la distance entre ces villes. On cherche à déterminer le plus court trajet pour aller de la ville A à la ville J.
Étape 1 : à partir de la ville A, 3 villes sont accessibles, B, C, et E qui se voient donc affectées des poids respectifs de 85,217, 173, tandis que les autres villes sont affectées d’une distance infinie. | Étape 2 : la distance la plus courte est celle menant à la ville B. Le passage par la ville B ouvre la voie à la ville F (85+80 = 165). |
Étape 3 : La distance la plus courte suivante est celle menant à la ville F. Le passage par la ville F ouvre une voie vers la ville I (415). | Étape 4 : La distance la plus courtesuivante est alors celle menant à la ville E. Le passage par la ville E ouvre une voie vers la ville J (675). |
Étape 5 : la distance la plus courte suivante mène alors à la ville C. Le passage par la ville C ouvre une voie vers la ville G (403) et la ville H (320). | Étape 6: la distance la plus courte suivante mène à ville H(320). Le passage par la ville H ouvre une voie vers la ville D et…