Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Algorithme de Dijkstra

L'algorithme de Dijkstra résout un problème du plus court chemin pour un graphe G(V,E) orienté et connexe dont le poids liés aux arcs sont positifs (>=0).

L'algorithme porte le nom de son inventeur, l'informaticien néerlandais Edsger Dijkstra.

Notations

L'ensemble V est l'ensemble de tous les nœuds dans le graphe G. L'ensemble E est l'ensemble des paires ordonnées de nœuds qui représentent les nœuds connectés dans le graphe (si (u,v) est inclus dans E, alors il existe une connexion (un arc) depuis le nœud u vers le nœud v).

Supposons que la fonction w: V x V → [0, ∞] décrive le coût w(x,y) du déplacement depuis le nœud x vers le nœud y (coût positif) (nous pouvons définir un coût infini pour les paires de nœuds qui ne sont pas connectées par un arc).

Principes

Le coût du chemin entre deux nœuds est la somme des coûts des arcs du chemin. Le coût d'un arc peut être vu comme (une généralisation de) la distance entre ces deux nœuds. Pour une paire donnée de nœuds s,t dans V, l'algorithme trouve le chemin depuis s vers t de moindre coût (autrement dit, le plus court chemin).

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

(a) en identifiant tous les arcs e_i = (v_i1,v_i2) dans G-S tel que v_i1 est dans S et v_i2 est dans G,

puis :

(b) en choisissant les arcs e_j = (v_j1,v_j2) dans G-S qui donne la distance minimum de ce nœud v_j2 (dans G) depuis s depuis tous les arcs e_i. L'algorithme se termine soit quand S devient un arbre spanning de G, soit quand tous les nœuds d'intérêt sont dans S.

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

Algorithmes

Quelques fonctions utilitaires pour l'algorithme de Dijkstra :

Initialize-Single-Source(G,s)
1 pour chaque vertex v dans V[G]
2 faire d[v] := infinite
3 previous[v] := 0
4 d[s] := 0

Relax(u,v,w)
1 si d[v] > d[u] + w(u,v)
2 alors d[v] := d[u] + w(u,v)
3 previous[v] := u

v = Extract-Min(Q) recherche pour le nœud v dans l'ensemble des nœuds Q 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.

La fonction principale a pour algorithme :

Dijkstra(G,w,s)
1 Initialize-Single-Source(G,s)
2 S := ensemble vide
3 Q := ensemble de tous les nœuds
4 tant que Q n'est pas un ensemble vide
5 faire u := Extract-Min(Q)
6 S := S union {u}
7 pour chaque nœud v voisin de u
8 faire Relax(u,v,w)

L'algorithme de Dijkstra peut-être mis en œuvre efficacement en stockant le graphe sous forme de listes adjacentes et en utilisant un tas comme une file à priorités pour réaliser la fonction Extract-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) :

Θ(m + n log n) 

Il est aussi possible de ne calculer que le plus court chemin entre deux nœuds s et t, en arrêtant la recherche à la ligne 5 de l'algorithme principal, lorsque l'égalité u = t est vérifiée.

Le plus court chemin de s à t peut donc se calculer par itération selon l'algorithme :

1 S = suite vide
2 u := t
3 S = u + S /* insert u au début de S */
4 si u == s
5 fin
6 u = previous[u]
7 goto 3

À la fin de cet algorithme, la suite S représente le plus court chemin de s à t.

Applications

OSPF Open shortest path first est une implémentation bien connue du monde réél utilisée dans le routage internet.

Un problème du même domaine est le problème du représentant de commerce, qui consiste à trouver le plus court chemin qui passe par chaque nœud d'un graphe connexe une et une seule fois, puis retourne au point de départ. Ce problème est, sous réserve que P soit différent de NP, d'une complexité non polynômiale, donc il ne peut pas être résolu dans un temps polynomial par l'algorithme de Dijkstra, ni par n'importe quel autre algorithme connu.

Références

Cormen, Leiserson, Rivest, Stein: Introduction à l'algorithmique

En Caml cet algorithme donne:

 let Dijkstra graphe sommet_initial sommet_final=
 let m=make_matrix (vect_length(graphe)) 4 0 and sommet_actuel=ref sommet_initial in
 for i=0 to vect_length(graphe)-1 do
 m.(i).(0)<-i+1;
 m.(i).(1)<-1000;
 m.(i).(2)<-0;
 m.(i).(3)<-0;
 done;
 m.(sommet_initial-1).(1)<-0;
 while m.(sommet_final-1).(2)=0 do
 let l=graphe.(!sommet_actuel-1) in
 let rec aux=function
 |[]->m.(!sommet_actuel-1).(2)<-1;
 |a::ll->if m.(!sommet_actuel-1).(1)+a.(1)<m.(a.(0)-1).(1) then
 begin
 m.(a.(0)-1).(1)<-m.(!sommet_actuel-1).(1)+a.(1);
 m.(a.(0)-1).(3)<-(!sommet_actuel);
 end; aux ll
 in
 aux l;
 let a=ref 1001 and b=ref 0 in
 for i=0 to vect_length(graphe)-1 do
 if (m.(i).(1)<(!a)) & (m.(i).(2))=0
 then begin b:=i+1; a:=m.(i).(1); end;
 done;
 sommet_actuel:=!b;
 done; 
 let rec chemin sommet=
 if sommet=sommet_initial then 
 [sommet_initial]
 else
 sommet::(chemin(m.(sommet-1).(3))) in
 (rev(chemin sommet_final),m.(sommet_final-1).(1));;

où graphe est un int vect list vect, c’est-à-dire un tableau constitué de listes de couples, les couples étant constitués du sommet adjacent et du poids de l'arête.