Algorithme de Dijkstra

Un article de Wikipédia, l'encyclopédie libre.
Cet article a une forme trop académique.
La forme ressemble trop à un extrait de cours et nécessite d'être réécrit afin de correspondre aux standards de l'encyclopédie. N'hésitez pas à l'améliorer.


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[1].

Sommaire

[modifier] 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 (s1,s2) est dans A, alors il existe une arête depuis le nœud s1 vers le nœud s2 ;
  • on définit la procédure Poids(s1,s2) définie sur A qui renvoie le poids positif de l'arête reliant s1 à s2 (et 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. Pour une paire donnée de sommets sdeb (le sommet du départ) sfin (sommet d'arrivée) appartenant à S, l'algorithme trouve le chemin depuis sdeb vers sfin 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 sdeb soit connue et soit 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 ai = (si1,si2) dans P \times G tel que si1 est dans P et si2 est dans G ;
2. en choisissant l'arête aj = (sj1,sj2) dans P \times G qui donne la distance minimum depuis sdeb à sj2 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êt[2] sont dans P.

[modifier] Algorithme

[modifier] Fonction annexes

L'algorithme utilise les fonctions annexes suivantes.

[modifier] 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 */[3]
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 */

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

[modifier] Mise à jour des distances

  • On met à jour des distances entre sdeb et s1 en se posant la question : vaut-il mieux passer par s2 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 */

[modifier] 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 sdeb à sfin peut ensuite se calculer itérativement selon l'algorithme suivant, avec A la suite représentant le plus court chemin de sdeb à sfin:

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   A = s + A
6   s = prédecesseur[s]       /* on continue de suivre le chemin */

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

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


Étape 1
Étape 1


Étape 2
Étape 2


Étape 3
Étape 3


Étape 4
Étape 4


Étape 5
Étape 5


Étape 6
Étape 6


Étape 7
Étape 7


Étape 8
Étape 8


Étape 9
Étape 9


[modifier] Codes

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

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

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

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

[modifier] Annexes

[modifier] Références

[modifier] Liens internes

[modifier] Liens externes

[modifier] Sources et indications supplémentaires

  1. ↑ (fr) « Principes de l'algorithme de Dijkstra ».
  2. ↑ 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.
  3. ↑ Les symboles /* ... */ représentent des commentaires.