L'algorithme de Dijkstra

L'algorithme de Dijkstra ( / ˈ d aɪ k s t r ə z / DYKE -strəz ) est un algorithme permettant de trouver les chemins les plus courts entre les nœuds d'un graphe pondéré , qui peut représenter, par exemple, des réseaux routiers . Il a été conçu par l'informaticien Edsger W. Dijkstra en 1956 et publié trois ans plus tard.

L'algorithme de Dijkstra trouve le chemin le plus court d'un nœud source donné à tous les autres nœuds. Il peut également être utilisé pour trouver le chemin le plus court vers un nœud de destination spécifique, en mettant fin à l'algorithme une fois que le chemin le plus court vers le nœud de destination est connu. Par exemple, si les nœuds du graphe représentent des villes et que les coûts des arêtes représentent les distances moyennes entre des paires de villes reliées par une route directe, alors l'algorithme de Dijkstra peut être utilisé pour trouver l'itinéraire le plus court entre une ville et toutes les autres villes. Une application courante des algorithmes de chemin le plus court est les protocoles de routage réseau , notamment IS-IS (Intermediate System to Intermediate System) et OSPF (Open Shortest Path First). Il est également utilisé comme sous-routine dans d'autres algorithmes tels que l'algorithme de Johnson .

L'algorithme utilise une structure de données de file d'attente à priorité minimale pour sélectionner les chemins les plus courts connus jusqu'à présent. Avant que des structures de file d'attente à priorité plus avancées ne soient découvertes, l'algorithme original de Dijkstra s'exécutait en temps , où est le nombre de nœuds. L'idée de cet algorithme est également donnée dans Leyzorek et al. 1957. Fredman & Tarjan 1984 ont proposé d'utiliser une file d'attente à priorité de tas de Fibonacci pour optimiser la complexité du temps d'exécution à . Il s'agit asymptotiquement de l'algorithme de chemin le plus court à source unique le plus rapide connu pour les graphes orientés arbitraires avec des poids non négatifs non bornés. Cependant, des cas spécialisés (tels que les poids bornés/entiers, les graphes acycliques dirigés, etc.) peuvent en effet être encore améliorés, comme détaillé dans Variantes spécialisées. De plus, si le prétraitement est autorisé, des algorithmes tels que les hiérarchies de contraction peuvent être jusqu'à sept ordres de grandeur plus rapides.

L'algorithme de Dijkstra est couramment utilisé sur les graphes où les poids des arêtes sont des entiers positifs ou des nombres réels. Il peut être généralisé à tout graphe où les poids des arêtes sont partiellement ordonnés , à condition que les étiquettes suivantes (une étiquette suivante est produite lors du passage d'une arête) soient monotones et non décroissantes.

Dans de nombreux domaines, notamment en intelligence artificielle , l'algorithme de Dijkstra ou une variante de celui-ci est connu sous le nom de recherche de coût uniforme et formulé comme un exemple de l'idée plus générale de recherche du meilleur en premier .

Quel est le chemin le plus court pour aller de Rotterdam à Groningue , en général : d'une ville donnée à une ville donnée. C'est l'algorithme du chemin le plus court , que j'ai conçu en une vingtaine de minutes. Un matin, je faisais du shopping à Amsterdam avec ma jeune fiancée, et fatigués, nous nous sommes assis à la terrasse d'un café pour boire une tasse de café et je me demandais si je pouvais le faire, et j'ai alors conçu l'algorithme du chemin le plus court. Comme je l'ai dit, c'était une invention de vingt minutes. En fait, il a été publié en 1959, trois ans plus tard. La publication est toujours lisible, elle est, en fait, assez belle. L'une des raisons pour lesquelles il est si beau est que je l'ai conçu sans crayon ni papier. J'ai appris plus tard qu'un des avantages de concevoir sans crayon ni papier est que vous êtes presque obligé d'éviter toutes les complexités évitables. Finalement, cet algorithme est devenu, à ma grande surprise, l'une des pierres angulaires de ma renommée.

—  Edsger Dijkstra, dans une interview avec Philip L. Frana, Communications of the ACM, 2001

Dijkstra a réfléchi au problème du chemin le plus court lorsqu'il travaillait au Centre de mathématiques d'Amsterdam en 1956 en tant que programmeur pour démontrer les capacités d'un nouvel ordinateur appelé ARMAC. Son objectif était de choisir à la fois un problème et une solution (qui serait produite par ordinateur) que les non-informaticiens pourraient comprendre. Il a conçu l'algorithme du chemin le plus court et l'a ensuite implémenté pour ARMAC pour une carte de transport légèrement simplifiée de 64 villes aux Pays-Bas (64, de sorte que 6 bits suffisent à coder le numéro de la ville). Un an plus tard, il a rencontré un autre problème chez les ingénieurs matériels travaillant sur le prochain ordinateur de l'institut : minimiser la quantité de fil nécessaire pour connecter les broches sur le panneau arrière de la machine. Comme solution, il a redécouvert l'algorithme connu sous le nom d'algorithme d'arbre couvrant minimal de Prim (connu auparavant de Jarník , et également redécouvert par Prim ). Dijkstra a publié l'algorithme en 1959, deux ans après Prim et 29 ans après Jarník.

Choisissons un nœud de départ et la distance du nœud N est la distance du nœud de départ à N. L'algorithme de Dijkstra commencera initialement avec des distances infinies et tentera de les améliorer étape par étape.

1. Marquer tous les nœuds comme non visités. Créer un ensemble de tous les nœuds non visités appelé ensemble non visité .
2. Attribuez à chaque nœud une distance par rapport à la valeur de départ : pour le nœud de départ, elle est nulle, et pour tous les autres nœuds, elle est infinie, car au départ aucun chemin n'est connu pour ces nœuds. Lors de l'exécution de l'algorithme, la distance d'un nœud N est la longueur du chemin le plus court découvert jusqu'à présent entre le nœud de départ et N. ]
3. Dans l'ensemble non visité, sélectionnez le nœud actuel comme étant celui ayant la plus petite distance finie ; initialement, ce sera le nœud de départ, qui a une distance de zéro. Si l'ensemble non visité est vide ou ne contient que des nœuds avec une distance infinie (qui sont inaccessibles), alors l'algorithme se termine en passant à l'étape 6. Si nous nous intéressons uniquement au chemin vers un nœud cible, nous pouvons nous arrêter ici si le nœud actuel est le nœud cible. Sinon, nous pouvons continuer à trouver les chemins les plus courts vers tous les nœuds accessibles.
4. Pour le nœud actuel, considérez tous ses voisins non visités et mettez à jour leurs distances via le nœud actuel ; comparez la distance nouvellement calculée à celle actuellement attribuée au voisin et attribuez-lui la plus petite. Par exemple, si le nœud actuel A est marqué avec une distance de 6 et que l'arête le reliant à son voisin B a une longueur de 2, alors la distance de B à A est de 6 + 2 = 8. Si B était précédemment marqué avec une distance supérieure à 8, mettez-la à jour à 8 (le chemin de B à A est plus court). Sinon, conservez sa distance actuelle (le chemin de B à A n'est pas le plus court).
5. Lorsque nous avons terminé de considérer tous les voisins non visités du nœud actuel, marquez le nœud actuel comme visité et supprimez-le de l'ensemble non visité. Cela permet d'éviter qu'un nœud visité ne soit plus jamais vérifié, ce qui est correct car la distance enregistrée sur le nœud actuel est minimale (comme assuré à l'étape 3), et donc définitive. Revenez à l'étape 3.
6. Une fois la boucle terminée (étapes 3 à 5), chaque nœud visité contiendra sa distance la plus courte à partir du nœud de départ.

Supposons que vous souhaitiez trouver le chemin le plus court entre deux intersections sur une carte de ville : un point de départ et une destination . L'algorithme de Dijkstra marque initialement la distance (du point de départ) à chaque autre intersection sur la carte avec l'infini . Cela n'implique pas qu'il existe une distance infinie, mais pour noter que ces intersections n'ont pas encore été visitées. Certaines variantes de cette méthode laissent les distances des intersections sans étiquette . Sélectionnez maintenant l' intersection actuelle à chaque itération. Pour la première itération, l'intersection actuelle sera le point de départ et la distance jusqu'à celle-ci (l'étiquette de l'intersection) sera zéro . Pour les itérations suivantes (après la première), l'intersection actuelle sera l' intersection non visitée la plus proche du point de départ (cela sera facile à trouver).

À partir de l'intersection actuelle, mettez à jour la distance jusqu'à chaque intersection non visitée qui lui est directement connectée. Pour ce faire, déterminez la somme de la distance entre une intersection non visitée et la valeur de l'intersection actuelle, puis réétiquetez l'intersection non visitée avec cette valeur (la somme) si elle est inférieure à la valeur actuelle de l'intersection non visitée. En effet, l'intersection est réétiquetée si le chemin qui y mène via l'intersection actuelle est plus court que les chemins connus précédemment. Pour faciliter l'identification du chemin le plus court, au crayon, marquez la route avec une flèche pointant vers l'intersection réétiquetée si vous l'étiquetez/réétiquetez, et effacez toutes les autres qui pointent vers elle. Après avoir mis à jour les distances jusqu'à chaque intersection voisine , marquez l'intersection actuelle comme visitée et sélectionnez une intersection non visitée avec une distance minimale (à partir du point de départ) - ou l'étiquette la plus basse - comme intersection actuelle. Les intersections marquées comme visitées sont étiquetées avec le chemin le plus court du point de départ jusqu'à celui-ci et ne seront pas revisitées ou reprises.

Continuez ce processus de mise à jour des intersections voisines avec les distances les plus courtes, en marquant l'intersection actuelle comme visitée et en passant à une intersection non visitée la plus proche jusqu'à ce que vous ayez marqué la destination comme visitée. Une fois que vous avez marqué la destination comme visitée (comme c'est le cas pour toute intersection visitée), vous avez déterminé le chemin le plus court pour y arriver à partir du point de départ et pouvez retracer votre chemin en suivant les flèches en sens inverse . Dans les implémentations de l'algorithme, cela se fait généralement (une fois que l'algorithme a atteint le nœud de destination) en suivant les parents des nœuds depuis le nœud de destination jusqu'au nœud de départ ; c'est pourquoi nous gardons également une trace du parent de chaque nœud.

Cet algorithme ne tente pas d'« explorer » directement la destination comme on pourrait s'y attendre. Au contraire, la seule considération pour déterminer la prochaine intersection « actuelle » est sa distance par rapport au point de départ. Cet algorithme s'étend donc vers l'extérieur à partir du point de départ, en considérant de manière interactive chaque nœud qui est plus proche en termes de distance du chemin le plus court jusqu'à ce qu'il atteigne la destination. Lorsqu'il est compris de cette manière, il est clair que l'algorithme trouve nécessairement le chemin le plus court. Cependant, cela peut également révéler l'une des faiblesses de l'algorithme : sa relative lenteur dans certaines topologies.

Dans le pseudo-code suivant , dist est un tableau qui contient les distances actuelles de la source aux autres sommets, c'est-à-dire que dist[ u ] est la distance actuelle de la source au sommet u . Le tableau prev contient des pointeurs vers les nœuds du saut précédent sur le chemin le plus court de la source au sommet donné (de manière équivalente, il s'agit du saut suivant sur le chemin du sommet donné à la source). Le code u ← vertex in Q avec min dist[u] , recherche le sommet u dans l'ensemble de sommets Q qui a la plus petite valeur dist[ u ] . Graph.Edges( u , v ) renvoie la longueur de l'arête joignant (c'est-à-dire la distance entre) les deux nœuds voisins u et v . La variable alt sur la ligne 14 est la longueur du chemin du nœud source au nœud voisin v s'il devait passer par u . Si ce chemin est plus court que le chemin le plus court actuel enregistré pour v , alors la distance de v est mise à jour à alt .

1 fonction Dijkstra( Graphe , source ): 2 3 pour chaque sommet v dans Graph.Vertices : 4 dist[ v ] ← INFINI 5 prev[ v ] ← INDÉFINI 6 ajouter v à Q 7 dist[ source ] ← 0 8 9 tant que 
Q n'est pas vide : 10 u ← sommet dans Q avec dist[u] minimum 11 supprimez-vous de Q 12 13 pour chaque voisin v de u toujours dans Q : 14 alt ← dist[ u ] + Graph.Edges( u , v ) 15 si 
alt < dist[ v ] : 16 dist[ v ] ← alt 17 précédent[ v ] ← u 18 19 retour dist[], prev[] 

Si nous nous intéressons uniquement au chemin le plus court entre les sommets source et target , nous pouvons terminer la recherche après la ligne 10 si u = target . Nous pouvons maintenant lire le chemin le plus court de la source à la cible par itération inverse :

1 S ← séquence vide 2 u ← target 3 if prev[ u ] is defined or 
u = source : // Faire quelque chose seulement si le sommet est atteignable 4 while 
u is defined: // Construire le chemin le plus court avec une pile S 5 insérer u au début de S 
// Pousser le sommet sur la pile 6 u ← prev[ u ] // Traverser de la cible à la source

Maintenant, la séquence S est la liste des sommets constituant l'un des chemins les plus courts de la source à la cible , ou la séquence vide si aucun chemin n'existe.

Un problème plus général serait de trouver tous les chemins les plus courts entre la source et la cible (il pourrait y en avoir plusieurs différents de la même longueur). Ensuite, au lieu de stocker un seul nœud dans chaque entrée de prev[], nous stockerions tous les nœuds satisfaisant la condition de relaxation. Par exemple, si r et la source se connectent à la cible et qu'ils se trouvent tous les deux sur des chemins les plus courts différents à travers la cible (parce que le coût des arêtes est le même dans les deux cas), alors nous ajouterions r et la source à prev[ target ] . Une fois l'algorithme terminé, la structure de données prev[] décrira en fait un graphe qui est un sous-ensemble du graphe d'origine avec quelques arêtes supprimées. Sa propriété clé sera que si l'algorithme a été exécuté avec un nœud de départ, alors chaque chemin de ce nœud à tout autre nœud du nouveau graphe sera le chemin le plus court entre ces nœuds du graphe d'origine, et tous les chemins de cette longueur du graphe d'origine seront présents dans le nouveau graphe. Ensuite, pour trouver réellement tous ces chemins les plus courts entre deux nœuds donnés, nous utiliserions un algorithme de recherche de chemin sur le nouveau graphique, tel que la recherche en profondeur .

Une file d'attente à priorité minimale est un type de données abstrait qui fournit 3 opérations de base : add_with_priority() , increase_priority() et extract_min() . Comme mentionné précédemment, l'utilisation d'une telle structure de données peut conduire à des temps de calcul plus rapides que l'utilisation d'une file d'attente de base. Notamment, le tas de Fibonacci ou la file d'attente Brodal offrent des implémentations optimales pour ces 3 opérations. Comme l'algorithme est légèrement différent en apparence, il est mentionné ici, également en pseudo-code :

1 fonction Dijkstra( Graphe , source ): 2 créer une file d'attente de priorité de vertex Q 3 4 dist[ source ] ← 0 // Initialisation 5 Q .add_with_priority( source , 0) // la priorité associée est égale à dist[·] 6 7 pour chaque sommet v dans Graph.Vertices : 8 si 
v ≠ source 9 prev[ v ] ← INDÉFINI // Prédécesseur de v 10 dist[ v ] ← INFINITÉ // Distance inconnue de la source à v 11 Q.add_with_priority(v, INFINITY) 12 13 14 tant que 
Q n'est pas vide : // La boucle principale 15 u ← Q .extract_min() // Supprimer et renvoyer le meilleur sommet 16 pour chaque voisin v de u : // Parcourir tous les voisins v de u 17 alt ← dist[ u ] + Graph.Edges( u , v ) 18 si 
alt < dist[ v ] : 19 précédent[ v ] ← u 20 dist[ v ] ← alt 21 Q .decrease_priority( v , alt ) 22 23 retour dist, précédent 

Au lieu de remplir la file d'attente prioritaire avec tous les nœuds de la phase d'initialisation, il est également possible de l'initialiser pour qu'elle ne contienne que la source ; alors, à l'intérieur du bloc, l' opération increase_priority() devient une opération add_with_priority() si le nœud n'est pas déjà dans la file d'attente. if alt < dist[v]

Une autre alternative consiste à ajouter des nœuds de manière inconditionnelle à la file d'attente prioritaire et à vérifier après l'extraction ( ) qu'il n'y a pas de revisite ou qu'aucune connexion plus courte n'a encore été trouvée dans le bloc. Cela peut être fait en extrayant en plus la priorité associée de la file d'attente et en ne traitant que plus loin dans la boucle. u ← Q.extract_min()if alt < dist[v]pif p == dist[u]while Q is not empty

Ces alternatives peuvent utiliser des files d'attente de priorité entièrement basées sur des tableaux sans fonctionnalité de diminution de clé, ce qui s'est avéré permettre des temps de calcul encore plus rapides dans la pratique. Cependant, la différence de performance s'est avérée plus faible pour les graphes plus denses.

Pour prouver la correction de l'algorithme de Dijkstra, nous procédons par induction mathématique sur le nombre de nœuds visités.

Hypothèse invariante : Pour chaque nœud visité v , est la distance la plus courte de la source à v , et pour chaque nœud non visité u , est la distance la plus courte de la source à u lorsque le trajet passe uniquement par les nœuds visités, ou l'infini si aucun chemin de ce type n'existe. (Remarque : nous ne supposons pas que est la distance la plus courte réelle pour les nœuds non visités, tandis que est la distance la plus courte réelle) dist[v]dist[u]dist[u]dist[v]

Cas de base :

Le cas de base est celui où il n'y a qu'un seul nœud visité, source . Sa distance est définie comme étant zéro, ce qui est la distance la plus courte, puisque les pondérations négatives ne sont pas autorisées. Par conséquent, l'hypothèse est valable.

Étape inductive :

Supposons que l'hypothèse soit valable pour les nœuds visités. Nous souhaitons montrer qu'elle est valable pour les nœuds. Soit u le prochain nœud visité selon l'algorithme, c'est-à-dire le nœud avec le minimum . Nous affirmons que est la distance la plus courte de la source à u . dist[u]dist[u]

Pour prouver cette affirmation, nous procédons par contradiction. S'il existait un chemin plus court, alors ce chemin plus court contiendrait ou non un autre nœud non visité.

• Français Dans le premier cas, soit w le premier nœud non visité sur ce chemin plus court. Par l'hypothèse d'induction, les chemins les plus courts de la source à u et w à travers les nœuds visités n'ont respectivement que des coûts et . Cela signifie que le coût pour aller de la source à u via w a un coût d'au moins + le coût minimal pour aller de w à u . Comme les coûts des arêtes sont positifs, le coût minimal pour aller de w à u est un nombre positif. Cependant, est au plus car sinon w aurait été choisi par la file d'attente prioritaire au lieu de v. C'est une contradiction, car il a déjà été établi que + un nombre positif < .dist[u]dist[w]dist[w]dist[u]dist[w]dist[w]dist[u]

• Dans le dernier cas, soit w l'avant-dernier nœud sur le chemin le plus court. Cela signifie . C'est une contradiction car au moment où w est visité, il aurait dû être fixé à au plus .dist[w] + Graph.Edges[w,u] < dist[u]dist[u]dist[w] + Graph.Edges[w,u]

Pour tous les autres nœuds visités v , on sait déjà que c'est la distance la plus courte par rapport à la source , en raison de l'hypothèse inductive, et ces valeurs restent inchangées. dist[v]

Après avoir traité u , il sera toujours vrai que pour chaque nœud non visité w , sera la distance la plus courte de la source à w en utilisant uniquement les nœuds visités. S'il existait un chemin plus court qui n'utilisait pas u , nous l'aurions trouvé auparavant, et s'il existait un chemin plus court utilisant u , nous l'aurions mis à jour lors du traitement de u . dist[w]

Une fois tous les nœuds visités, le chemin le plus court depuis la source vers n'importe quel nœud v ne comprend que les nœuds visités. Par conséquent, c'est la distance la plus courte. dist[v]

Les limites du temps d'exécution de l'algorithme de Dijkstra sur un graphe d'arêtes E et de sommets V peuvent être exprimées en fonction du nombre d'arêtes, noté , et du nombre de sommets, noté , en utilisant la notation big-O . La limite de complexité dépend principalement de la structure de données utilisée pour représenter l'ensemble Q . Dans ce qui suit, les limites supérieures peuvent être simplifiées car est pour tout graphe simple, mais cette simplification ne tient pas compte du fait que dans certains problèmes, d'autres limites supérieures de peuvent être respectées.

Pour toute structure de données pour l'ensemble de sommets Q , le temps d'exécution est dans

où et sont les complexités des opérations de diminution de clé et d'extraction de minimum dans Q , respectivement.

La version la plus simple de l'algorithme de Dijkstra stocke l'ensemble de sommets Q sous forme de liste chaînée ou de tableau, et les arêtes sous forme de liste d'adjacence ou de matrice . Dans ce cas, extract-minimum est simplement une recherche linéaire sur tous les sommets de Q , donc le temps d'exécution est .

Pour les graphes clairsemés , c'est-à-dire les graphes avec beaucoup moins d' arêtes, l'algorithme de Dijkstra peut être implémenté plus efficacement en stockant le graphe sous forme de listes d'adjacence et en utilisant un arbre de recherche binaire auto-équilibré , un tas binaire , un tas d'appariement ou un tas de Fibonacci comme file d'attente prioritaire pour implémenter efficacement l'extraction du minimum. Pour effectuer efficacement les étapes de diminution de la clé dans un tas binaire, il est nécessaire d'utiliser une structure de données auxiliaire qui mappe chaque sommet à sa position dans le tas, et de maintenir cette structure à jour lorsque la file d'attente prioritaire Q change. Avec un arbre de recherche binaire auto-équilibré ou un tas binaire, l'algorithme nécessite

temps dans le pire des cas ; pour les graphes connectés, cette limite de temps peut être simplifiée en . Le tas de Fibonacci améliore cela en

Lors de l'utilisation de tas binaires, la complexité temporelle moyenne du cas est inférieure à celle du pire des cas : en supposant que les coûts des arêtes sont tirés indépendamment d'une distribution de probabilité commune , le nombre attendu d' opérations de diminution de clé est limité par , ce qui donne un temps d'exécution total de

Dans les présentations courantes de l'algorithme de Dijkstra, tous les nœuds sont initialement placés dans la file d'attente prioritaire. Cela n'est cependant pas nécessaire : l'algorithme peut démarrer avec une file d'attente prioritaire qui ne contient qu'un seul élément et insérer de nouveaux éléments au fur et à mesure qu'ils sont découverts (au lieu de faire une diminution de clé, vérifier si la clé est dans la file d'attente ; si c'est le cas, diminuer sa clé, sinon l'insérer). Cette variante a les mêmes limites de pire cas que la variante courante, mais maintient une file d'attente prioritaire plus petite dans la pratique, ce qui accélère les opérations de file d'attente.

De plus, le fait de ne pas insérer tous les nœuds dans un graphe permet d'étendre l'algorithme pour trouver le chemin le plus court d'une source unique au plus proche d'un ensemble de nœuds cibles sur des graphes infinis ou trop grands pour être représentés en mémoire. L'algorithme résultant est appelé recherche à coût uniforme (UCS) dans la littérature sur l'intelligence artificielle et peut être exprimé en pseudo-code comme

procédure uniform_cost_search(start) est nœud ← début frontière ← file d'attente prioritaire contenant uniquement le nœud développé ← ensemble vide faire 
si la frontière est vide alors 
renvoyer un échec nœud ← frontière.pop() si le nœud est un état objectif , alors 
renvoie la solution (nœud) développé.add(nœud) pour chacun des voisins du nœud n 
, 
si 
n n'est pas développé et n'est pas à la frontière, alors frontier.add( n ) sinon si 
n est à la frontière avec un coût plus élevé remplacer le nœud existant par n

La complexité de cet algorithme peut être exprimée d'une manière alternative pour les graphes très grands : lorsque C ^* est la longueur du chemin le plus court depuis le nœud de départ jusqu'à tout nœud satisfaisant le prédicat « but », chaque arête a un coût au moins ε et le nombre de voisins par nœud est limité par b , alors la complexité temporelle et spatiale du pire des cas de l'algorithme sont toutes deux en O ( b ^{1+⌊ C * ⁄ ε ⌋} ) .

D'autres optimisations de l'algorithme de Dijkstra pour le cas à cible unique incluent des variantes bidirectionnelles , des variantes orientées vers un objectif telles que l' algorithme A* (voir § Problèmes et algorithmes associés), l'élagage du graphe pour déterminer quels nœuds sont susceptibles de former le segment médian des chemins les plus courts (routage basé sur la portée) et les décompositions hiérarchiques du graphe d'entrée qui réduisent le routage s – t à la connexion de s et t à leurs « nœuds de transit » respectifs, suivis du calcul du chemin le plus court entre ces nœuds de transit à l'aide d'une « autoroute ». Des combinaisons de telles techniques peuvent être nécessaires pour des performances pratiques optimales sur des problèmes spécifiques.

Lorsque les poids des arcs sont de petits entiers (bornés par un paramètre ), des files spécialisées qui tirent parti de ce fait peuvent être utilisées pour accélérer l'algorithme de Dijkstra. Le premier algorithme de ce type était l'algorithme de Dial (Dial 1969) pour les graphes avec des poids d'arêtes entiers positifs, qui utilise une file d'attente à compartiments pour obtenir un temps d'exécution . L'utilisation d'un arbre de Van Emde Boas comme file d'attente prioritaire porte la complexité à (Ahuja et al. 1990). Une autre variante intéressante basée sur une combinaison d'un nouveau tas de base et du tas de Fibonacci bien connu s'exécute dans le temps (Ahuja et al. 1990). Enfin, les meilleurs algorithmes dans ce cas particulier sont les suivants. L'algorithme donné par (Thorup 2000) s'exécute dans le temps et l'algorithme donné par (Raman 1997) s'exécute dans le temps.

La fonctionnalité de l'algorithme original de Dijkstra peut être étendue avec une variété de modifications. Par exemple, il est parfois souhaitable de présenter des solutions qui sont moins qu'optimales mathématiquement. Pour obtenir une liste classée des solutions moins qu'optimales, la solution optimale est d'abord calculée. Une arête unique apparaissant dans la solution optimale est supprimée du graphique, et la solution optimale de ce nouveau graphique est calculée. Chaque arête de la solution originale est supprimée à son tour et un nouveau chemin le plus court est calculé. Les solutions secondaires sont ensuite classées et présentées après la première solution optimale.

L'algorithme de Dijkstra est généralement le principe de fonctionnement des protocoles de routage à état de liens , OSPF et IS-IS étant les plus courants.

Contrairement à l'algorithme de Dijkstra, l' algorithme de Bellman-Ford peut être utilisé sur des graphes avec des poids d'arêtes négatifs, tant que le graphe ne contient aucun cycle négatif accessible à partir du sommet source s . La présence de tels cycles signifie qu'il n'y a pas de chemin le plus court, puisque le poids total diminue à chaque fois que le cycle est parcouru. (Cette affirmation suppose qu'un « chemin » est autorisé à répéter des sommets. En théorie des graphes, cela n'est normalement pas autorisé. En informatique théorique, c'est souvent autorisé.) Il est possible d'adapter l'algorithme de Dijkstra pour gérer les arêtes de poids négatif en le combinant avec l'algorithme de Bellman-Ford (pour supprimer les arêtes négatives et détecter les cycles négatifs) ; un tel algorithme est appelé algorithme de Johnson .

L' algorithme A* est une généralisation de l'algorithme de Dijkstra qui réduit la taille du sous-graphe à exploré, si des informations supplémentaires sont disponibles qui fournissent une limite inférieure sur la « distance » à la cible.

Le processus qui sous-tend l'algorithme de Dijkstra est similaire au processus glouton utilisé dans l'algorithme de Prim . L'objectif de Prim est de trouver un arbre couvrant minimal qui relie tous les nœuds du graphe ; Dijkstra ne s'intéresse qu'à deux nœuds. Prim n'évalue pas le poids total du chemin à partir du nœud de départ, mais uniquement les arêtes individuelles.

La recherche en largeur peut être considérée comme un cas particulier de l'algorithme de Dijkstra sur des graphes non pondérés, où la file d'attente prioritaire dégénère en une file d'attente FIFO.

La méthode de marche rapide peut être considérée comme une version continue de l'algorithme de Dijkstra qui calcule la distance géodésique sur un maillage triangulaire.

D'un point de vue de programmation dynamique , l'algorithme de Dijkstra est un schéma d'approximation successive qui résout l'équation fonctionnelle de programmation dynamique pour le problème du plus court chemin par la méthode Reaching .

En fait, l'explication de Dijkstra sur la logique derrière l'algorithme, à savoir

Problème 2. Trouver le chemin de longueur totale minimale entre deux nœuds donnés et .

Nous utilisons le fait que, si est un nœud sur le chemin minimal de à , la connaissance de ce dernier implique la connaissance du chemin minimal de à .

est une paraphrase du principe d'optimalité de Bellman dans le contexte du problème du chemin le plus court.