Algorithme de Dijkstra

Infos
L'algorithme de Dijkstra sert à résoudre le problème du plus court chemin entre deux sommets d'un graphe connexe dont le poids lié aux arêtes est positif ou nul. Pour illustrer l'intérêt de cet 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
Algorithme de Dijkstra

L'algorithme de Dijkstra sert à résoudre le problème du plus court chemin entre deux sommets d'un graphe connexe dont le poids lié aux arêtes est positif ou nul. Pour illustrer l'intérêt de cet 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 néerlandais Edsger Dijkstra et a été publié en 1959 « »..

Notations

Le graphe est noté G=(S, A) où :
-l'ensemble S est l'ensemble des sommets du graphe G ;
-l'ensemble A est l'ensemble des arêtes de G tel que : si (s_1, s_2) est dans A, alors il existe une arête depuis le nœud s_1 vers le nœud s_2 ;
-on définit la procédure Poids(s_1, s_2) définie sur A qui renvoie le poids positif de l'arête reliant s_1 à s_2 (et un poids infini pour les paires de sommets qui ne sont pas connectées par une arête).

Principes

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 s_ (le sommet du départ) s_ (sommet d'arrivée) appartenant à S, l'algorithme trouve le chemin depuis s_ vers s_ de moindre poids (autrement dit le chemin le plus léger ou encore le plus court). L'algorithme fonctionne en construisant un sous-graphe P de manière à ce que la distance entre un sommet s de P depuis s_ soit connue et soit un minimum dans G. Initialement P contient simplement le nœud s_ isolé, et la distance de s_ à lui-même vaut zéro. Des arcs sont ajoutés à P à chaque étape : :1. en identifiant toutes les arêtes a_i=(s_, s_) dans P \times G tel que s_ est dans P et s_ est dans G ; :2. en choisissant l'arête a_j=(s_, s_) dans P \times G qui donne la distance minimum depuis s_ à s_ en passant tous les chemins créés menant à ce nœud. L'algorithme se termine soit quand P devient un arbre couvrant de G, soit quand tous les nœuds d'intérêtPar 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. sont dans P.

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 := infini /
- on initialise les sommets autres que sdeb à 0
-/Les symboles /
- ...
-/ représentent des commentaires. 3 prédecesseur := 0 /
- car on ne connaît au départ aucun chemin entre s et sdeb
-/ 4 d := 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 s_ parmi les nœuds situés dans un ensemble Q, constitué des nœuds éloigné d'une arête des éléments de P. On utilise pour cela la fonction Trouve_min. Le nœud trouvé est alors effacé de l'ensemble Q et est alors retourné à la fonction principale comme résultat de la fonction.

Mise à jour des distances

- On met à jour des distances entre s_ et s_ en se posant la question : vaut-il mieux passer par s_ ou pas ? maj_distances(s1, s2) 1 si d > d + Poids(s1, s2) 2 alors d := d + Poids(s1, s2) 3 prédecesseur := s1 /
- on fait passer le chemin par s1
-/

Fonction principale

Voici la fonction principale utilisant les précédentes fonctions annexes : Dijkstra(G, Poids, sdeb) 1 Initialisation(G, sdeb) 2 P := ensemble vide 3 Q := ensemble de tous les nœuds 4 tant que Q n'est pas un ensemble vide 5 faire s1 := Trouve_min(Q) 6 P := P union 7 pour chaque nœud s2 voisin de s1 8 faire maj_distances(s1, s2) Le plus court chemin de s_ à s_ peut ensuite se calculer itérativement selon l'algorithme suivant, avec A la suite représentant le plus court chemin de s_ à s_: 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 /
- 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é s_1=s_ est vérifiée, à condition bien sûr de ne chercher que la distance minimale entre s_ et s_. 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 Trouve_min. Si le graphe possède m arcs et n nœuds, en supposant que les comparaisons des poids d'arcs soient à temps constant, alors la complexité de l'algorithme est : \sigma . On notera que l'utilisation de tas de Fibonacci donne un meilleur temps d'exécution amorti : \sigma .

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 (Frankfurt) à Munich (München). Étape 1 Étape 2 Étape 3 Étape 4 Étape 5 Étape 6 Étape 7 Étape 8 Étape 9

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 DejaVu = liste vide PasEncoreVu = nœuds Tant que PasEncoreVu != liste vide n1 = minimum(PasEncoreVu) // Le nœud dans PasEncoreVu avec parcouru le plus petit DejaVu.ajouter(n1) 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 à n2, il faut passer par n1 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 Retourner chemin Fin fonction Dijkstra

Implémentation Caml

Voici le code d'implémentation Caml : (
- 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)

Applications

Une application des plus courantes de l'algorithme de Dijkstra est le protocole open shortest path first qui permet un 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 saison 3.

Annexes

Références

- , contenant l'article original décrivant l'algorithme de Dijkstra (pages 67 à 73)
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein : « Introduction à l'algorithmique », (version deuxième édition, 2001, MIT Press and McGraw-Hill, section 24.3, « Dijkstra's algorithm », pages 595–601) ===
Sujets connexes
Algorithme A*   Algorithme de Dantzig-Ford   Algorithme de Ford-Bellman   Algorithme de parcours en largeur   Algorithmique   Allemagne   Arbre couvrant de poids minimal   Caml   Complexité   Edsger Dijkstra   File à priorités   Francfort-sur-le-Main   IS-IS   Informaticien   Munich   NUMB3RS   Pays-Bas   Problèmes de cheminement   Routage   Tas   Tas de Fibonacci   Théorie des graphes  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^