Algorithme de Dijkstra
26685
31476320
2008-07-10T19:18:36Z
132.207.108.180
/* Fonction principale */ : Erreur dans l'ordre des deux dernieres instructions : d'abord chercher le predecesseur, ensuite ajouter le predecesseur a la liste resultat
{{À désacadémiser}}
L''''algorithme de Dijkstra''' sert à résoudre le problème du plus court chemin entre deux sommets d'un [[théorie des graphes |graphe]] [[Algorithmes de connexité|connexe]] dont le poids lié aux [[théorie des graphes#Définition intuitive|arêtes]] est positif ou nul.
Pour illustrer l'intérêt de cet [[algorithmique|algorithme]], on peut prendre pour exemple le réseau routier d'une région : chaque sommet est une ville et chaque arc est une route dont le poids est le kilométrage. L'algorithme de Dijkstra permet alors de trouver le plus court chemin d'une ville à une autre.
L'algorithme porte le nom de son inventeur, l'[[informaticien]] [[Pays-Bas|néerlandais]] [[Edsger Dijkstra]] et a été publié en 1959<ref>{{fr}} « ''[http://www.nimbustier.net/publications/djikstra/djikstra.html Principes de l'algorithme de Dijkstra]'' ».</ref>.
== Notations ==
Le graphe est noté <math>G=(S,A)</math> où :
*l'ensemble <math>S</math> est l'ensemble des sommets du graphe <math>G</math> ;
*l'ensemble <math>A</math> est l'ensemble des arêtes de <math>G</math> tel que : si <math>(s_1,s_2)</math> est dans <math>A</math>, alors il existe une arête depuis le nœud <math>s_1</math> vers le nœud <math>s_2</math> ;
*on définit la procédure <math>Poids(s_1,s_2)</math> définie sur <math>A</math> qui renvoie le poids positif de l'arête reliant <math>s_1</math> à <math>s_2</math> (et un poids infini pour les paires de sommets qui ne sont pas connectées par une arête).
== Principes ==
[[Image:Dijkstra's algorithm.svg|right|100px]]
Le poids du chemin entre deux sommets est la somme des poids des arêtes qui le composent. Pour une paire donnée de sommets <math>s_{deb}</math> (le sommet du départ) <math>s_{fin}</math> (sommet d'arrivée) appartenant à <math>S</math>, l'algorithme trouve le chemin depuis <math>s_{deb}</math> vers <math>s_{fin}</math> de moindre poids (autrement dit le chemin le plus léger ou encore le plus court).
L'algorithme fonctionne en construisant un sous-graphe <math>P</math> de manière à ce 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 toutes les arêtes <math>a_i=(s_{i1},s_{i2})</math> dans <math>P \times G</math> tel que <math>s_{i1}</math> est dans <math>P</math> et <math>s_{i2}</math> est dans <math>G</math> ;
:'''2.''' en choisissant l'arête <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>.
{{clr}}
== Algorithme ==
===Fonction annexes===
L'algorithme utilise les fonctions annexes suivantes.
====Initialisation de l'algorithme====
Initialisation(G,sdeb)
1 '''pour''' chaque point s de G
2 '''faire''' d[s] := infini /* on initialise les sommets autres que sdeb à 0 */<ref>Les symboles /* ... */ représentent des commentaires.</ref>
3 prédecesseur[s] := 0 /* car on ne connaît au départ aucun chemin entre s et sdeb */
4 d[sdeb] := 0 /* sdeb étant le point le plus proche de sdeb */
====Recherche du nœud le plus proche====
* On recherche le nœud le plus proche (relié par l'arête de poids le plus faible) de <math>s_{deb}</math> parmi les nœuds situés dans un ensemble <math>Q</math>, constitué des nœuds éloigné d'une arête des éléments de <math>P</math>. On utilise pour cela la fonction <tt>Trouve_min()</tt>. Le nœud trouvé est alors effacé de l'ensemble <math>Q</math> et est alors retourné à la fonction principale comme résultat de la fonction.
====Mise à jour des distances====
* On met à jour des distances entre <math>s_{deb}</math> et <math>s_{1}</math> en se posant la question : vaut-il mieux passer par <math>s_{2}</math> ou pas ?
maj_distances(s1,s2)
1 '''si''' d[s2] > d[s1] + Poids(s1,s2)
2 '''alors''' d[s2] := d[s1] + Poids(s1,s2)
3 prédecesseur[s2] := s1 /* on fait passer le chemin par s2 */
===Fonction principale===
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
4 '''faire''' s1 := Trouve_min(Q)
5 Q := Q privé de s1
6 '''pour''' chaque nœud s2 voisin de s1
7 '''faire''' maj_distances(s1,s2)
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 suite représentant le plus court chemin de <math>s_{deb}</math> à <math>s_{fin}</math>:
1 A = suite vide
2 s := sfin
3 A = s + A /* insère s au début de A */
4 '''tant que''' s != sdeb
5 s = prédecesseur[s] /* on continue de suivre le chemin */
6 A = s + A
===Améliorations de l'algorithme===
Il est possible d'améliorer légèrement l'algorithme principal en arrêtant la recherche lorsque l'égalité <math>s_1=s_{fin}</math> est vérifiée, à condition bien sûr de ne chercher que la distance minimale entre <math>s_{deb}</math> et <math>s_{fin}</math>.
L'algorithme de Dijkstra pourra être mis en œuvre efficacement en stockant le graphe sous forme de listes d'adjacence et en utilisant un [[tas]] comme une [[file à priorités]] pour réaliser la fonction <tt>Trouve_min</tt>.
Si le graphe possède <math>m</math> arcs et <math>n</math> nœuds, en supposant que les comparaisons des poids d'arcs soient à temps constant, alors la [[complexité]] de l'algorithme est : <math>\sigma [(m+n)\times ln(n)]</math>. On notera que l'utilisation de [[tas de Fibonacci]] donne un meilleur temps d'exécution amorti : <math>\sigma [m+n\times ln(n)]</math>.
==Exemple==
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 en [[Allemagne]] et les arêtes indiquent la distance entre les villes. On veut aller de [[Francfort-sur-le-Main|Francfort]] (''Frankfurt'') à [[Munich]] (''München'').
[[Image:DijkstraStep01.svg|350px|left|thumb|Étape 1]] <br style="clear:both;">
[[Image:DijkstraStep02.svg|350px|left|thumb|Étape 2]] <br style="clear:both;">
[[Image:DijkstraStep03.svg|350px|left|thumb|Étape 3]] <br style="clear:both;">
[[Image:DijkstraStep04.svg|350px|left|thumb|Étape 4]] <br style="clear:both;">
[[Image:DijkstraStep05.svg|350px|left|thumb|Étape 5]] <br style="clear:both;">
[[Image:DijkstraStep06.svg|350px|left|thumb|Étape 6]] <br style="clear:both;">
[[Image:DijkstraStep07.svg|350px|left|thumb|Étape 7]] <br style="clear:both;">
[[Image:DijkstraStep08.svg|350px|left|thumb|Étape 8]] <br style="clear:both;">
[[Image:DijkstraStep09.svg|350px|left|thumb|Étape 9]] <br style="clear:both;">
== Codes ==
===Pseudo-code===
fonction Dijkstra (nœuds, fils, distance, debut, fin)
Pour n parcourant nœuds
n.parcouru = infini // Peut être implémenté avec -1
n.precedent = 0
Fin pour
debut.parcouru = 0
PasEncoreVu = nœuds
Tant que PasEncoreVu != liste vide
n1 = minimum(PasEncoreVu) // Le nœud dans PasEncoreVu avec parcouru le plus petit
PasEncoreVu.enlever(n1)
Pour n2 parcourant fils(n1) // Les nœuds reliés à n1 par un arc
Si n2.parcouru > n1.parcouru + distance(n1, n2) // distance correspond au poids de l'arc reliant n1 et n2
n2.parcouru = n1.parcouru + distance(n1, n2)
n2.precedent = n1 // Dis que pour aller à n1, il faut passer par n2
Fin si
Fin pour
Fin tant que
chemin = liste vide
n = fin
Tant que n != debut
chemin.ajouterAvant(n)
n = n.precedent
Fin tant que
chemin.ajouterAvant(debut)
Retourner chemin
Fin fonction Dijkstra
===Implémentation Caml===
Voici le code d'implémentation [[Caml]] :
<source lang="ocaml">
(* on suppose données des files de priorité *)
module H : sig
type 'a t
val empty : 'a t
val is_empty : 'a t -> bool
val add : int * 'a -> 'a t -> 'a t
val extract_min : 'a t -> (int * 'a) * 'a t
end
(* l'adjacence est donnée sous la forme d'une fonction : adj v est la liste des voisins de v,
avec leur distance ; la fonction suivante cherche le plus court chemin de v1 à v2 *)
let dijkstra (adj: 'a -> ('a * int) list) (v1:'a) (v2:'a) =
let visited = Hashtbl.create 97 in
let rec loop h =
if H.is_empty h then raise Not_found;
let (w,(v,p)),h = H.extract_min h in
if v = v2 then
List.rev p, w
else
let h =
if not (Hashtbl.mem visited v) then begin
Hashtbl.add visited v ();
List.fold_left (fun h (e,d) -> H.add (w+d, (e, e::p)) h) h (adj v)
end else
h
in
loop h
in
loop (H.add (0,(v1,[])) H.empty)
</source>
== Applications ==
Une application des plus courantes de l'algorithme de Dijkstra est le protocole ''[[OSPF|open shortest path first]]'' qui permet un [[routage|routage internet]] très efficace des informations en cherchant le parcours le plus efficace.
Les routeurs ''[[IS-IS]]'' utilisent également l'algorithme. Les sites d'itinéraires routiers l'utilisent de la même manière et permettent de nombreuses adaptations en ajustant le poids des arcs comme par exemple : trajet le plus économique, le plus rapide...
==Apparition dans la culture populaire==
L'algorithme de Dijkstra est utilisé par les enquêteurs de la série [[NUMB3RS]], dans l'épisode 23 de la [[NUMB3RS : saison 3|saison 3]].
==Annexes==
===Références===
* {{en}} [http://www.cs.utexas.edu/users/EWD/ewd03xx/EWD316.PDF « ''A short introduction to the art of programming'' » de Edsger W. Dijkstra], contenant l'article original décrivant l'algorithme de Dijkstra (pages 67 à 73)
* {{fr}} [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]] et [[Clifford Stein]] : « ''Introduction à l'algorithmique'' », (version {{en}} {{ISBN|0-262-03293-7}} deuxième édition, 2001, MIT Press and McGraw-Hill, section 24.3, « ''Dijkstra's algorithm'' », pages 595–601)
===Liens internes===
* [[Edsger Dijkstra]]
*''[[Pathfinding]]'' et [[Problèmes de cheminement]]
*[[Algorithme de parcours en largeur]]
*[[Algorithme A*]]
*Articles sur l'[[algorithme de Dantzig-Ford]] et l'[[algorithme de Ford-Bellman]] qui permettent de calculer le plus court chemin avec des poids d'arêtes négatifs
===Liens externes===
* {{fr}} [http://www.nimbustier.net/publications/djikstra/index.html Explication détaillée de l'algorithme de Dijkstra et implémentation complète en C++]
* {{fr}} [http://www.opencity.info/pdf/AG41_OpenCity_ShortestPath_Report.pdf Rapport sur l'algorithme de Dijkstra et le jeu de simulation OpenCity]
* {{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.]
===Sources et indications supplémentaires===
<references />
{{Portail|mathématiques|informatique}}
[[Catégorie:Algorithme de la théorie des graphes|Dijkstra]]
[[Catégorie:Algorithme de recherche]]
[[bg:Алгоритъм на Дейкстра]]
[[cs:Dijkstrův algoritmus]]
[[de:Dijkstra-Algorithmus]]
[[en:Dijkstra's algorithm]]
[[es:Algoritmo de Dijkstra]]
[[fa:الگوریتم دایجکسترا]]
[[fi:Dijkstran algoritmi]]
[[he:אלגוריתם דייקסטרה]]
[[hu:Dijkstra-algoritmus]]
[[id:Algoritma Dijkstra]]
[[it:Algoritmo di Dijkstra]]
[[ja:ダイクストラ法]]
[[ko:데이크스트라 알고리즘]]
[[lt:Dijkstros algoritmas]]
[[nl:Kortstepadalgoritme]]
[[no:Dijkstras algoritme]]
[[pl:Algorytm Dijkstry]]
[[pt:Algoritmo de Dijkstra]]
[[ro:Algoritmul lui Dijkstra]]
[[ru:Алгоритм Дейкстры]]
[[sk:Dijkstrov algoritmus]]
[[sl:Dijkstrov algoritem]]
[[sr:Дијкстрин алгоритам]]
[[sv:Dijkstras algoritm]]
[[uk:Алгоритм Дейкстри]]
[[vi:Thuật toán Dijkstra]]
[[zh:迪科斯彻算法]]