Algorithme de Dijkstra

Algorithme de Dijkstra

L'algorithme de Dijkstra pour trouver le chemin le plus court entre a et b. Il choisit le sommet non visité avec la distance la plus faible, calcule la distance à travers lui à chaque voisin non visité, et met à jour la distance du voisin si elle est plus petite. Il marque le sommet visité (en rouge) lorsqu'il a terminé avec les voisins.

Découvreur ou inventeur	Edsger Dijkstra
Date de découverte	1959[1]
Problèmes liés	Algorithme de recherche de chemin (d), algorithme de la théorie des graphes (en), algorithme glouton, algorithme
Structure des données	Graphe
Basé sur	Algorithme de parcours en largeur
À l'origine de	Algorithme A*, link-state routing protocol (en), Open Shortest Path First, IS-IS

Complexité en temps

Pire cas	Pour un graphe à ${\displaystyle n}$ sommets et ${\displaystyle m}$ arcs : ${\displaystyle O((n+m)\log(n))}$ pour l'implémentation avec un tas binaire, ${\displaystyle O(m+n\log(n))}$ pour l'implémentation avec un tas de Fibonacci

modifier - modifier le code - modifier Wikidata

En théorie des graphes, l'algorithme de Dijkstra (prononcé [dɛɪkstra]) sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer un plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Plus précisément, il calcule des plus courts chemins à partir d'une source vers tous les autres sommets dans un graphe orienté pondéré par des réels positifs. On peut aussi l'utiliser pour calculer un plus court chemin entre un sommet de départ et un sommet d'arrivée.

L'algorithme porte le nom de son inventeur, l'informaticien néerlandais Edsger Dijkstra, et a été publié en 1959^[2].

La complexité temporelle de l'algorithme de Dijkstra dépend de la structure de données utilisée pour la file de priorité :

• Avec une file de priorité implémentée par un tas binaire : la complexité est en ${\displaystyle {\mathcal {O}}\left({\vphantom {X^{X}}}(E+v)\;\log(v)\right)}$, où ${\displaystyle E}$ est le nombre d'arêtes et ${\displaystyle v}$ le nombre de sommets du graphe.
• Avec une file de priorité implémentée par un tas de Fibonacci : la complexité est améliorée à ${\displaystyle {\mathcal {O}}\left({\vphantom {X^{X}}}(E+v)\;\log(v)\right)}$.

Ces complexités s'appliquent aux graphes avec des poids d'arêtes positifs. Pour les graphes comportant des arêtes de poids négatif, l'algorithme de Bellman-Ford est généralement préféré.