Voir la source de Algorithme de Dijkstra

{{Infobox Algorithme
 | temps max             = Pour un graphe à <math>n</math> sommets et <math>m</math> arcs :

<math>O((n+m)\log(n))</math> pour l'implémentation avec un [[tas binaire]],
<math>O(m + n\log(n))</math> pour l'implémentation avec un [[tas de Fibonacci]]
}}
En [[théorie des graphes]], l''''algorithme de Dijkstra''' (prononcé {{API|[dɛɪkstra]}}) sert à résoudre le [[problèmes de cheminement|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]] [[Pays-Bas|néerlandais]] [[Edsger Dijkstra]], et a été publié en 1959<ref>{{article
| auteur = Dijkstra, E. W. 
| année = 1959
| titre = A note on two problems in connexion with graphs
| périodique = [[Numerische Mathematik]]
| volume =  1
| pages = 269–271
| doi= 10.1007/BF01386390.
}}.</ref>.

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 <math>\mathcal{O}\left(\vphantom{X^X}(E+v)\;\log(v)\right)</math>, où <math>E</math> est le nombre d'arêtes et <math>v</math> 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 à <math>\mathcal{O}\left(\vphantom{X^X}(E+v)\;\log(v)\right)</math>.

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é.

== Problème du plus court chemin ==
L'algorithme de Dijkstra permet de résoudre un [[problème algorithmique]] : le [[problème du plus court chemin]]. Ce problème a plusieurs variantes. La plus simple est la suivante : étant donné un [[graphe non-orienté]], dont les arêtes sont munies de poids, et deux sommets de ce graphe, trouver un [[Chaîne (théorie des graphes)|chemin]] entre les deux sommets dans le graphe, de poids minimum. L'algorithme de Dijkstra permet de résoudre un problème plus général : le graphe peut être [[graphe orienté|orienté]], et l'on peut désigner un unique sommet, et demander d'avoir la liste des plus courts chemins pour tous les autres nœuds du graphe.

== Principe sur un exemple ==
L'algorithme prend en entrée un graphe orienté pondéré par des réels positifs et un sommet source. Il s'agit de construire progressivement un sous-graphe dans lequel sont classés les différents sommets par ordre croissant de leur [[distance (théorie des graphes)|distance]] minimale au sommet de départ. La distance correspond à la somme des poids des arcs empruntés.

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 nulle. 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).

=== Distance entre la ville A et la ville J ===
{{Animation
|titre=Animation d'un algorithme de Dijkstra
|float= right
|upright=1.5
|image1=DijkstraBis01.svg|légende1=Étape 1 : 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.
|image2=DijkstraBis02.svg|légende2=Étape 2 : 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.
|image3=DijkstraBis03.svg|légende3=Étape 3 : on choisit F. On met à jour le voisin I (415).
|image4=DijkstraBis04.svg|légende4=Étape 4 : on choisit E. On met à jour le voisin J (675).
|image5=DijkstraBis05.svg|légende5=Étape 5 : 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).
|image6=DijkstraBis06.svg|légende6=Étape 6 : 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).
|image7=DijkstraBis07.svg|légende7=Étape 7 : la distance la plus courte suivante est celle de la ville G. On choisit G. La mise à jour ne change aucune autre distance.
|image8=DijkstraBis08.svg|légende8=Étape 8 : 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).
|image9=DijkstraBis09.svg|légende9=Étape 9 : 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.
}}
L'algorithme de Dijkstra fonctionne aussi sur un graphe non orienté. L'exemple ci-contre 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.

En neuf étapes, on peut déterminer le chemin le plus court menant de A à J, il passe par C et H et mesure {{unité|487|km}}.

=== Présentation 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. Une ligne donne les distances courantes des sommets depuis le sommet de départ. 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.

{| class="wikitable" style="text-align:center; width:80%;"
|+ Algorithme de Dijkstra
|-
! scope=col |
!à A
! scope=col | à B
! scope=col | à C
! scope=col | à D
! scope=col | à E
! scope=col | à F
! scope=col | à G
! scope=col | à H
! scope=col | à I
! scope=col | à J
|-
!étape initiale
!0
!∞
!∞
!∞
!∞
!∞
!∞
!∞
!∞
!∞
|-
! scope="row" | A(0)
|
| {{Souligner|85 }}
| 217 
| ∞ 
| 173
| ∞ 
| ∞ 
| ∞ 
| ∞ 
| ∞ 
|-
! scope="row" | B(85<sub>A</sub>)
|
| - 
| 217 
| ∞ 
| 173 
| {{Souligner|165 }}
| ∞ 
| ∞ 
| ∞ 
| ∞ 
|-
! scope="row" | F(165<sub>B</sub>)
|
| - 
| 217 
| ∞ 
| {{Souligner|173}} 
| - 
| ∞ 
| ∞ 
| 415 
| ∞ 
|-
! scope="row" | E(173<sub>A</sub>)
|
| - 
| {{Souligner|217 }}
| ∞ 
| - 
| - 
| ∞ 
| ∞ 
| 415 
| 675 
|-
! scope="row" | C(217<sub>A</sub>)
|
| - 
| -
| ∞ 
| - 
| - 
| 403 
| {{Souligner|320 }}
| 415 
| 675 
|-
! scope="row" | H(320<sub>C</sub>)
|
| - 
| -
| 503 
| - 
| - 
| {{Souligner|403 }}
| -
| 415 
| <s>675</s> 487 
|-
! scope="row" | G(403<sub>C</sub>)
|
| - 
| -
| 503 
| - 
| - 
| -
| -
| {{Souligner|415 }}
| 487 
|-
! scope="row" | I(415<sub>F</sub>)
|
| - 
| -
| 503 
| - 
| -
| -
| -
| -
|{{Souligner|487}}
|-
! scope="row" | J(487<sub>H</sub>)
|
| - 
| -
| {{Souligner|503 }}
| - 
| -
| -
| -
| -
| -
|-
! scope="row" | D(503<sub>H</sub>)
|
| - 
| -
| -
| - 
| -
| -
| -
| -
| -
|-

|}

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.

== Schéma de l'algorithme ==
[[Image:Dijkstra's algorithm.svg|right|100px]]
Le graphe est noté <math>G=(S,A)</math> où :
* l'ensemble <math>S</math> est l'ensemble fini des sommets du graphe <math>G</math> ;
* l'ensemble <math>A</math> est l'ensemble des arcs de <math>G</math> tel que : si <math>(s_1, s_2)</math> est dans <math>A</math>, alors il existe un arc depuis le nœud <math>s_1</math> vers le nœud <math>s_2</math> ;
* on définit la fonction <math>poids</math> définie sur <math>S \times S</math> dans <math>\mathbb{R}^+\cup\{+\infty\}</math> qui à un couple <math>(s_1, s_2)</math> associe le poids positif <math>poids(s_1,s_2)</math> de l'arc reliant <math>s_1</math> à <math>s_2</math> (et <math>+\infty</math> s'il n'y a pas d'arc reliant <math>s_1</math> à <math>s_2</math>).
Le poids du chemin entre deux sommets est la somme des poids des arcs qui le composent. Pour une paire donnée de sommets <math>s_{deb}</math> (le sommet du départ) <math>s_{fin}</math> (le sommet d'arrivée) appartenant à <math>S</math>, l'algorithme trouve un chemin depuis <math>s_{deb}</math> vers <math>s_{fin}</math> de moindre poids (autrement dit un chemin le plus léger ou encore le plus court).

L'algorithme fonctionne en construisant un sous-graphe <math>P</math> de manière que la distance entre un sommet <math>s</math> de  <math>P</math> depuis <math>s_{deb}</math> soit connue et soit un minimum dans <math>G</math>. Initialement, <math>P</math> contient simplement le nœud <math>s_{deb}</math> isolé, et la distance de <math>s_{deb}</math> à lui-même vaut zéro. Des arcs sont ajoutés à <math>P</math> à chaque étape :

:'''1.''' en identifiant  tous les arcs <math>a_i=(s_{i1},s_{i2})</math> dans <math>P \times G</math>;
:'''2.''' en choisissant l'arc <math>a_j=(s_{j1},s_{j2})</math> dans <math>P \times G</math> qui donne la distance minimum depuis <math>s_{deb}</math> à <math>s_{j2}</math> en passant tous les chemins créés menant à ce nœud.

L'algorithme se termine soit quand <math>P</math> devient un [[Arbre couvrant de poids minimal|arbre couvrant]] de <math>G</math>, soit quand tous les nœuds d'intérêt<ref>Par exemple, les nœuds n'ayant pas d'arêtes autres que celle que l'on a parcourue pour arriver à eux, ne sont pas considérés comme des nœuds d'intérêt.</ref> sont dans <math>P</math>.

On peut donc écrire l'algorithme de la façon suivante :

 Entrées : <math>G=( S,A )</math> un graphe avec une pondération positive <math>poids</math> des arcs, <math>s_{deb}</math> un sommet de <math>S</math>
 
 <math>P := \emptyset</math>
 <math>d[a] := + \infty</math> pour chaque sommet <math>a</math>
 <math>d[s_{deb}] = 0</math>
 Tant qu'il existe un sommet hors de <math>P</math>
     Choisir un sommet <math>a</math> hors de <math>P</math> de plus petite distance <math>d[a]</math>
     Mettre <math>a</math> dans <math>P</math> 
     Pour chaque sommet <math>b</math> hors de  <math>P</math> voisin de <math>a</math>
        Si d[b] > d[a] + poids(a, b)
            <math>d[b] = d[a] + poids(a, b)</math>
            prédécesseur[b] := a
     Fin Pour
 Fin Tant Que

{{clr}}

== Implémentation de l'algorithme ==
=== Fonctions annexes ===
L'algorithme utilise les fonctions annexes suivantes.
==== Initialisation de l'algorithme ====
 Initialisation(G,sdeb)
 1 '''pour''' chaque point s de G '''faire'''
 2    d[s] := infini             /* on initialise les sommets autres que sdeb à infini */<ref>La suite de caractères /* ... */ est un [[Commentaire (informatique)|commentaire]].</ref>
 3 '''fin pour'''
 4 d[sdeb] := 0                  /* la distance au sommet de départ sdeb est nulle */

==== Recherche d'un nœud de distance minimale ====
* On recherche un nœud de distance minimale (relié par l'arc de poids le plus faible) de <math>s_{deb}</math> parmi les nœuds situés hors de  <math>P</math>. Le complémentaire de <math>P</math> est noté <math>Q</math>. On implémente pour cela une fonction <tt>Trouve_min(Q)</tt> qui choisit un nœud de <tt>Q</tt> de distance minimale.
 Trouve_min(Q)
 1 mini := infini
 2 sommet := -1
 3 '''pour''' chaque sommet s de Q
 4    '''si''' d[s] < mini
 5    '''alors''' 
 <nowiki>6        mini := d[s]</nowiki>
 7        sommet := s
 8 '''fin pour'''
 9 renvoyer sommet

==== Mise à jour des distances ====
* On met à jour les distances entre <math>s_{deb}</math> et <math>s_{2}</math> en se posant la question : vaut-il mieux passer par <math>s_{1}</math> ou pas ?
 maj_distances(s1,s2)
 1 '''si''' d[s2] > d[s1] + Poids(s1,s2)      /* Si la distance de sdeb à s2 est plus grande que */
 2                                      /* celle de sdeb à S1 plus celle de S1 à S2 */
 3    '''alors''' 
 4        d[s2] := d[s1] + Poids(s1,s2) /* On prend ce nouveau chemin qui est plus court */
 5        prédécesseur[s2] := s1        /* En notant par où on passe */

=== Fonction principale ===
{{Style non encyclopédique section|date=décembre 2017}}

Voici la fonction principale utilisant les précédentes fonctions annexes :

 Dijkstra(G,Poids,sdeb)
 1 Initialisation(G,sdeb)
 2 Q := ensemble de tous les nœuds
 3 '''tant que''' Q n'est pas un ensemble vide '''faire'''
 4       s1 := Trouve_min(Q)
 5       Q := Q privé de s1
 6       '''pour''' chaque nœud s2 voisin de s1 '''faire'''
 7           maj_distances(s1,s2)
 8       '''fin pour'''
 9 '''fin tant que'''

Le plus court chemin de <math>s_{deb}</math> à <math>s_{fin}</math> peut ensuite se calculer itérativement selon l'algorithme suivant, avec <math>A</math> la liste représentant le plus court chemin de <math>s_{deb}</math> à <math>s_{fin}</math>:
 1 A := suite vide
 2 s := sfin
 3 '''tant que''' s != sdeb '''faire'''
 4   A := cons(s, A)            /* on ajoute s en tête de la liste A */
 5   s := prédécesseur[s]       /* on continue de suivre le chemin */
 6 '''fin tant que'''
 7 A := cons(sdeb, A)           /* on ajoute le nœud de départ */

Attention : s'il n'y a pas de chemin de <math>s_{deb}</math> à <math>s_{fin}</math> cette partie de l'algorithme fait une [[boucle infinie]] ou une erreur selon votre implémentation.

=== Spécialisation de l'algorithme ===

Il est possible de spécialiser l'algorithme en arrêtant la recherche lorsque l'égalité <math>s_1=s_{fin}</math> est vérifiée, dans le cas où on ne cherche que la distance minimale entre <math>s_{deb}</math> et <math>s_{fin}</math>.

== Complexité de l'algorithme ==
L'efficacité de l'algorithme de Dijkstra repose sur une mise en œuvre efficace de <tt>Trouve_min</tt>. L'ensemble <math>Q</math> est implémenté par une [[file à priorités]]. Si le graphe possède <math>|A|</math> arcs et <math>|S|</math> nœuds, qu'il est représenté par des [[Liste d'adjacence|listes d'adjacence]] et si on implémente la file à priorités par un [[tas binaire]] (en supposant que les comparaisons des poids d'arcs soient en temps constant), alors la [[complexité en temps]] de l'algorithme est <math>O((|A|+|S|)\times\log(|S|))</math>. En revanche, si on implémente la file à priorités avec un [[tas de Fibonacci]], l'algorithme est en <math>O(|A|+|S|\times\log(|S|))</math><ref name=":0">{{Harvsp|Cormen|Leiserson|Rivest|Stein|2010|p = 610}}</ref>.

== Correction de l'algorithme ==
La démonstration de correction est une récurrence sur Card(''P'') (qui augmente de 1 à chaque itération) et repose sur l'invariant suivant :

<math>\begin{cases}\forall c \in P,\,d(c)=mini(c)\\ \forall c \not\in P,\,d(c) = miniP(c) \end{cases}</math>

où :
* mini(''c'') est le poids d'un plus court chemin menant à ''c'' ;
* miniP(''c'') est le poids d'un plus court chemin dont tous les sommets intermédiaires sont dans ''P'' menant à ''c''.

Si ''n'' = Card(''P''), la preuve est la suivante :
* pour ''n'' = 0 et 1 : immédiat ;
* pour ''n'' un entier non nul, supposons l'invariant vrai.

L'algorithme sélectionne un pivot <math>a \not\in P</math> tel que <math>d(a) = \underset{x\not\in P}{Min} \, d(x)</math>, et l'ajoute dans P. Il faut donc montrer que <math>d(a)=mini(a)</math> après modification de P:

Par hypothèse, <math>d(a)=miniP(a)</math> avant modification de ''P'', donc s'il existe un chemin ''C'' tel que <math>poids(C) < d(a)</math> alors ce chemin contient au moins un sommet ''b'' <math>\neq  </math> ''a'' tel que <math>b \not\in P</math>.

Soit donc un tel sommet ''b'' tel que tous ses prédécesseurs dans ''C'' soient dans ''P'' (il existe car le premier sommet de ''C'' est l'origine qui est dans ''P''). Décomposons ''C'' en ''Cb''- et ''Cb''+ où ''Cb''- est la première partie de ''C'' dont le dernier sommet est ''b'', et ''Cb''+ la suite de ''C''. Alors <math>poids(C) = poids(Cb-) + poids(Cb+) \geq poids(Cb-) = d(b) \geq d(a)</math> : contradiction.

Il n'existe donc aucun chemin ''C'' tel que <math>poids(C) < d(a)</math> d'où <math>d(a) = mini(a)</math>. L'égalité est toujours vraie pour les autres éléments de ''P''.

Enfin, l'algorithme met à jour la fonction ''d'' (et prédécesseur) pour les successeurs ''b'' du pivot ''a'' : <math>d[b] = \min( d[b], d[a] + poids(a, b) )</math>.

Montrons qu'alors, <math>\forall c \not\in P,\,d(c) = miniP(c)</math> :

* si ''c'' n'est pas un successeur du pivot ''a'', alors il n'existe aucun nouveau chemin ''C'' menant à ''c'' tel que <math>poids(C) < d(c)</math> et dont tous les sommets intermédiaires sont dans ''P'' après l'ajout de ''a'' dans ''P'' puisqu'il faudrait alors passer par ''a'' avant de passer par un autre sommet <math>d\in P</math>, mais ce ne serait pas le plus court chemin jusqu'à ''d'' puisque le poids du plus court chemin jusqu'à ''d'' a déjà été calculé avant l'ajout de ''a'' dans ''P'' par hypothèse, et ce chemin ne contient donc que des sommets ayant été dans ''P'' avant l'ajout de ''a'' dans ''P'' ;

* sinon, il existe de tels chemins, en notant ''C'' le meilleur d'entre eux, alors ''C'' sera un des nouveaux chemins engendrés par l'ingestion du pivot ''a'' par ''P'', donc <math>a \in C</math> et d'autre part le pivot ''a'' est le dernier sommet intermédiaire de ''C''  puisque le plus court chemin menant aux autres sommets de ''P'' ne passe par ''a'' comme expliqué plus haut. ''C'' est donc la réunion du plus court chemin menant à ''a'' avec l'arc (''a'', ''c'') : d'où <math>poids(C) = d(c) = poids((a,c)) + d(a) =  miniP(c)</math>.

== Applications ==
L'algorithme de Dijkstra trouve une utilité dans le calcul des itinéraires routiers. Le poids des arcs pouvant être la distance (pour le trajet le plus court), le temps estimé (pour le trajet le plus rapide), la consommation de carburant et le prix des péages (pour le trajet le plus économique). {{référence nécessaire}}

Une application courante de l'algorithme de Dijkstra apparaît dans les [[Interior Gateway Protocol|protocoles de routage interne]] « à état de liens », tels que ''{{lang|en|[[Open Shortest Path First]]}}'' ({{lang|en|OSPF}})<ref>{{Lien web |langue=en |auteur=John Moy |titre=RFC2328 OSPF Version 2 |url=https://tools.ietf.org/html/rfc2328#page-161 |mois=04 |année=1998 |site= |citation=''{{lang|en|Using the Dijkstra algorithm, a tree is formed from this subset of the link state database.}}''|page=161|consulté le=19 mai 2016}}</ref> ou ''{{lang|en|[[IS-IS]]}}''<ref>{{Lien web |langue=en |auteur=David R. Oran |titre=RFC1142 : OSI IS-IS Intra-domain Routing Protocol |url=https://tools.ietf.org/html/rfc1142 |mois=02 |année=1990 |site= |citation=''{{lang|en|An algorithm invented by Dijkstra (see references) known as shortest path first (SPF), is used as the basis for the route calculation.}}''|consulté le=19 mai 2016}}</ref> – ou encore {{lang|en|{{lien|PNNI}}}} sur les réseaux [[Asynchronous Transfer Mode|ATM]] –, {{référence nécessaire|qui permettent un [[routage|routage internet]] très efficace des informations en cherchant le parcours le plus efficace.}}

== Comparaison avec d'autres algorithmes ==
* L'algorithme de Dijkstra est fondé sur un [[parcours en largeur]].
* La spécialisation de l'algorithme de Dijkstra qui calcule un plus court chemin d'une source à une destination est une instance de l'[[algorithme A*]] dans lequel la fonction heuristique est la [[fonction nulle]]. L'algorithme A* qui utiliserait une heuristique minorante et monotone (par exemple la distance à vol d'oiseau) peut être plus efficace {{référence souhaitée}}.
* L'algorithme ne s'applique pas aux graphes avec des poids négatifs. Mais l'[[algorithme de Bellman-Ford]] permet de résoudre le problème des plus courts chemins depuis une source avec des poids négatifs (mais sans cycle négatif). 
* L'[[algorithme de Floyd-Warshall]] calcule des plus courts chemins entre tous les sommets dans un graphe où les poids peuvent être négatifs.

== Notes et références ==
{{Références}}

== Annexes ==
{{Autres projets|wiktionary=algorithme de Dijkstra}}
=== Bibliographie ===
* {{en}} [http://www.cs.utexas.edu/users/EWD/ewd03xx/EWD316.PDF « ''A short introduction to the art of programming'' » de Edsger W. Dijkstra], 1971, contenant l'article original (1959) décrivant l'algorithme de Dijkstra (pages 67 à 73).
* {{Cormen2en}}, section 24.3, « ''Dijkstra's algorithm'' », pages 595–601.
* {{Cormen3fr}}

=== Articles connexes ===
* [[Lexique de la théorie des graphes]]
* [[Recherche de chemin]] et [[Problèmes de cheminement]]
* [[Algorithme de parcours en largeur]]
* [[Algorithme A*]]
* Article sur l'[[algorithme de Ford-Bellman]] qui permet de calculer le plus court chemin avec des poids d'arcs négatifs

=== Liens externes ===
* [http://www.nimbustier.net/publications/djikstra/index.html Explication détaillée de l'algorithme de Dijkstra et implémentation complète en C++]
* [http://www.gilles-bertrand.com/2014/03/dijkstra-algorithm-python-example-source-code-shortest-path.html Explication détaillée de l'algorithme de Dijkstra et implémentation complète en Python]
* {{en}} [http://students.ceid.upatras.gr/~papagel/project/kef5_7_1.htm Applet Java montrant l'algorithme de Dijkstra étape par étape]
* {{en}} [http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml Applets Java utilisant l'algorithme]

{{Palette|Algorithmes sur les graphes}}
{{Portail|informatique théorique}}

[[Catégorie:Algorithme de la théorie des graphes|Dijkstra]]
[[Catégorie:Algorithme de recherche]]