Algorithme de Dijkstra

Un article de Wikipédia, l'encyclopédie libre.

L'algorithme de Dijkstra résout le problème du plus court chemin pour un graphe G=(S,A) connexe dont le poids lié aux arêtes est positif ou nul (Pour les arêtes de poids quelconque, l'Algorithme de Ford-Bellman peut être utilisé).

On peut prendre pour exemple le réseau routier d'une région: chaque sommet est une ville, 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.

[modifier] Notations

L'ensemble S est l'ensemble des sommets du graphe G. L'ensemble A est l'ensemble des arêtes de G : si (s₁,s₂) est dans A, alors il existe une arête depuis le nœud s₁ vers le nœud s₂.

Supposons que la fonction Poids(s₁,s₂) définie sur A renvoie le poids positif de l'arête reliant s₁ à s₂ (nous pouvons définir un poids infini pour les paires de sommets qui ne sont pas connectées par une arête).

[modifier] Principes

Le poids du chemin entre deux sommets est la somme des poids des arêtes qui le composent. Le poids d'une arête peut être vu comme (une généralisation de) la distance entre ces deux sommets. Pour une paire donnée de sommets sdeb (sommet du départ) et sfin (sommet d'arrivée) dans S, l'algorithme trouve le chemin depuis sdeb vers sfin de moindre poids (autrement dit, le plus court chemin).

L'algorithme fonctionne en construisant un sous-graphe P tel que la distance entre un sommet s de P depuis sdeb est connue pour être un minimum dans G. Initialement P contient simplement le nœud sdeb isolé, et la distance de sdeb à lui-même vaut zéro. Des arcs sont ajoutés à P à chaque étape :

1. en identifiant toutes les arêtes a_i = (s_i1,s_i2) dans GxP tel que s_i1 est dans P et s_i2 est dans G,

2. en choisissant l' arête a_j = (s_j1,s_j2) dans GxP qui donne la distance minimum de ce nœud s_j2 (dans G) depuis sdeb depuis tous les arcs e_i.

L'algorithme se termine soit quand P devient un arbre couvrant de G, soit quand tous les nœuds d'intérêt sont dans P.

La procédure pour ajouter un arc s_j à P conserve la propriété suivante : les distances de tous les nœuds dans P depuis sdeb sont des minimums connus.

[modifier] Algorithme

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
3       prédecesseur[s] := 0     /*car on ne connait au départ aucun chemin entre s et sdeb*/
4 d[sdeb] := 0                   /*sdeb est le point le plus proche de sdeb!*/

Recherche du nœud le plus proche de sdeb dans Q: Trouve_min(Q) recherche dans l'ensemble des nœuds Q celui qui a la plus faible valeur d[v]. Ce nœud est effacé de l'ensemble Q et est alors retourné comme valeur résultat de la fonction.
Mise à jour des distances entre sdeb et s2 à (vaut-il mieux passer par s1 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 s1*/

La fonction principale a alors pour algorithme :

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 {s1}
7          pour chaque nœud  s2 voisin de s1
8              faire maj_distances(s1,s2)

Le plus court chemin de sdeb à sfin peut ensuite se calculer itérativement selon l'algorithme suivant, avec S la suite représentant le plus court chemin de sdeb à sfin:

1 S = suite vide
2 s := sfin
3 S = s + S              /* insère s au début de  S */
4 tant que s != sdeb
5   s = prédecesseur[s]  /*On continue de suivre le chemin*/
6   S = s + S

Il est possible d'améliorer légèrement l'algorithme principal en arrêtant la recherche lorsque l'égalité s1 = sfin est vérifiée, à condition bien sûr de ne chercher que la distance minimale entre sdeb et sfin.

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, alors la complexité de l'algorithme est (en supposant que les comparaisons des poids d'arcs soient à temps constant): $\theta (m+n\times ln(n))$ . On notera que l'utilisation de tas binomiaux ou mieux de tas de Fibonacci donne un meilleur temps d'exécution amorti.

[modifier] 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) à Münich (München).

[modifier] Étape 1

Étape 1

[modifier] Étape 2

Étape 2

[modifier] Étape 3

Étape 3

[modifier] Étape 4

Étape 4

[modifier] Étape 5

Étape 5

[modifier] Étape 6

Étape 6

[modifier] Étape 7

Étape 7

[modifier] Étape 8

Étape 8

[modifier] Étape 9

Étape 9

[modifier] 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

[modifier] Applications

Une application des plus courantes est le protocole Open shortest path first qui permet un routage internet très efficace des informations en cherchant le parcours le plus efficace via Dijkstra.

Les sites d'itinéraires routiers utilisent entre autres cet algorithme, et permettent de nombreux raffinements (ex: trajet le plus économique, le plus rapide...) en ajustant les poids des arcs.

[modifier] 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)

[modifier] Références

(fr) Cormen, Leiserson, Rivest, Stein : Introduction à l'algorithmique

[modifier] Liens extérieurs

(fr) Applet java à but pédagogique implémentant l'algorithme de Dijkstra

http://www.mathiaz.com/routage/

Portail des mathématiques – Accédez aux articles de Wikipédia concernant les mathématiques.

Récupérée de « http://fr.wikipedia.org../../../a/l/g/Algorithme_de_Dijkstra_f8c4.html »

Catégories : Algorithme de la théorie des graphes • Algorithme de recherche