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:迪科斯彻算法]]