Algorithme de Dijkstra
L'algorithme porte le nom de son inventeur, l'informaticien néerlandais Edsger Dijkstra.
| Sommaire |
Notations
L'ensemble S est l'ensemble des sommets du graphe G. L'ensemble A est l'ensemble des arètes de G (couples de sommets : si (s1,s2) est inclus dans A, alors il existe une arête depuis le nœud s1 vers le nœud s2).
Supposons que la fonction Poids(s1,s2) définie sur A renvoie le poids positif de l'arête reliant s1 à s2 (nous pouvons définir un poids infini pour les paires de sommets qui ne sont pas connectées par une arête).
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 et sfin 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 S tel que la distance entre un sommet s (dans S) depuis sdeb est connue pour être un minimum dans G. Initialement S contient simplement le nœud sdeb isolé, et la distance de sdeb à lui-même vaut zéro. Des arcs sont ajoutés à S à chaque étape :
- 1. en identifiant toutes les arêtes ai = (si1,si2) dans GxS tel que si1 est dans S et si2 est dans G,
- 2. en choisissant l' arête aj = (sj1,sj2) dans GxS qui donne la distance minimum de ce nœud sj2 (dans G) depuis sdeb depuis tous les arcs ei.
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 sj à S conserve la propriété suivante : les distances de tous les nœuds dans S depuis sdeb sont des minimums connus.
Algorithmes
Quelques fonctions utilitaires pour l'algorithme de Dijkstra :
- 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!*/
- Mise à jour des distances entre sdeb et s2 à (vaut-il passer mieux 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*/
- 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.
La fonction principale a pour algorithme :
Dijkstra(G,Poids,sdeb)
1 Initialiation(G,sdeb)
2 S := 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 S := S 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 /* insert s au début de S */ 4 si s == sfin fin 5 sinon 6 s = prédecesseur[s] /*On continue de suivre le chemin*/ 7 goto 3
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 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 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) :
Θ(m + n log n)
Applications
OSPF Open shortest path first est une implémentation bien connue du monde réel utilisée dans le routage internet.
Un problème du même domaine est le problème du voyageur 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.
Implémentation Caml
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.
Références
Cormen, Leiserson, Rivest, Stein: Introduction à l'algorithmique
Liens extérieurs
- http://www.nimbustier.net/publications/djikstra/index.html Explication détaillée de l'algorithme de Dijkstra et implémentation complète en C++
- http://students.ceid.upatras.gr/~papagel/project/kef5_7_1.htm (en anglais) Un applet Java montrant l'algorithme de Dijkstra étape par étape