Soit un graphe ayant n sommets numérotés de 0 à n−1. Certains de ces
sommets sont reliés par des arêtes de longueur données.
L’algorithme de Dijkstra permet de trouver le chemin de distance minimale qui
relie le sommet de numéro deb aux autres sommets.
Cet algorithme procéde de proche en proche en se servant de la remarque :
si par exemple, le chemin le plus court pour aller du sommet 0 au sommet 2
passe par le sommet 4, le début de ce chemin est aussi le chemin le plus
court pour aller du sommet 0 au sommet 4.
Soient n=4 et le graphe de matrice A :
| A= | ⎛ ⎜ ⎜ ⎜ ⎝ |
| ⎞ ⎟ ⎟ ⎟ ⎠ |
Je veux partir du sommet 0 pour aller au sommet 1 (resp 2,3) par le plus court
chemin.
J’initialise :
dist à [0,27,11,23] (c’est à dire à la ligne 0 de A)
afaire à [1,2,3] et
sprec à [-1,0,0,0] (sprec[0]=-1 car on part du sommet 0 et
pour j!=0, sprec[j]=0 car dist est la distance provisoire
minimum pour aller de 0 à j). Les 2 valeurs dist[0] et
sprec[0] sont définitives car le sommet 0 est ici le départ. Je sais
aussi que le chemin le plus court du sommet 0 au sommet 1 (resp 2,3) ne
repassera pas par le sommet 0.
Première étape
Je cherche le minimum des valeurs de dist pour les
sommets dont les numéros sont dans afaire=[1,2,3] c’est à dire le
minimum de [27,11,23].
Le minimum 11 de [27,11,23] est réalisé pour le sommet 2 (car
dist[2]=11). Je supprime le numéro 2 de la liste afaire qui
devient afaire=[1,3] car je connais maintenant
le plus court chemin pour aller de 0 à 2, il est direct
et a pour longueur 11 je ne change donc pas la valeur de dist[2] ni celle de sprec[2] : ces 2 valeurs sont maintenant définitives.
On a donc encore dist=[0,27,11,23] et sprec=[-1,0,0,0] où les
valeurs d’indice 0 et 2 sont définitives.
Maintenant, le chemin provisoirement le plus court allant du sommet 0 au sommet
1 (resp du sommet 0 au sommet 3) est :
L’étape suivante consiste donc à comparer le chemin le plus court de 0 à
2 de longueur dist[2], suivi par le chemin direct de 2 à 1 de longueur
A[2,1] (resp 3 de longueur A[2,3]) avec le chemin le plus court
provisoire qui va de 0 à 1 dist[1] (respde 0 à 3 dist[3]).
Je compare donc 27=dist[1] à 11+14=25 (11=dist[2]=longueur du
chemin minimum allant de 0 à 2 et 14=A[2,1]=longueur du chemin direct
allant de 2 à 1). On a 25<27 donc je modifie dist en [0,25,11,23]
et sprec en [-1,2,0,0] puisque 25 est la longueur du chemin qui
passe par 2.
Je compare donc 23=dist[3] à 11+10=21 (11=longueur du chemin
minimum allant de 0 à 2 et 10=A[2,3]=longueur du chemin direct allant
de 2 à 3). On a 21<23 donc je modifie
dist en [0,25,11,21] et sprec en [-1,2,0,2] puisque 21
est la longueur du chemin qui passe par 2.
Donc maintenant dist=[0,25,11,21] et sprec=[-1,2,0,2]
Deuxième étape
Je cherche le minimum des valeurs de dist pour les
sommets de numéros afaire=[1,3] c’est à dire le minimum de
[25,21].
Le minimum 21 de [25,21] est réalisé pour le sommet 3 car
dist[3]=21. Je supprime le numéro 3 de la liste afaire qui
devient afaire=[1] car je connais maintenant
le plus court chemin pour aller de 0 à 3, il est de
longueur 21 et il passe par 2 car sprec[3]=2.
Je cherche enfin le plus court chemin pour aller de 0 à 1 en empruntant :
Je compare donc 25 à 22. On a 22<25 donc je modifie
dist en [0,22,11,21] et sprec en [-1,3,0,2].
Donc maintenant dist=[0,22,11,21] et sprec=[-1,3,0,2]
Troisième étape
Il reste à chercher le minimum de [22] est obtenu pour le sommet de
numéro 1, numéro que l’on supprime de la liste afaire qui devient
vide.
Le résultat final est donc :
dist=[0,22,11,21] et sprec=[-1,3,0,2]
Soit A la matrice donnant la longueur des arêtes i.e. A[j,k] est
la longueur de l’arête reliant le sommet j au sommet k avec la
convention de mettre A[j,k]=inf=+∞ quand il n’y a pas d’arête
qui relie le sommet j au sommet k.
Soientt dist un vecteur donnant les distances provisoires reliant le
sommet de numéro deb aux autres sommets et sprec[j] le
numéro du sommet précedent j par lequel on doit passer pour avoir la
distance minimale provisoire.
Par exemple si n=5 et si en fin de programme sprec=[3,2,0,-1,2]
cela veut dire que l’on part du sommet 3 car sprec[3]=-1.
Si on cherche le plus court chemin pour aller du sommet 3 au sommet j=4
le chemin sera 3,???,4. Mais comme sprec[4]=2 le chemin sera 3,??,2,4 puis, comme sprec[2]=0 et sprec[0]=3 le chemin sera
3,0,2,4.
Par contre le chemin minimum pour aller du sommet 3 à 0 sera
direct de 3 à 0 puique sprec[0]=3.
afaire est la liste des indices restant à faire.
Initialisation :
Au début dist=A[deb] (A[deb] est la ligne d’indice deb de
A) et
sprec[deb]=-1 et sprec[j]=deb pour j!:=deb.
afaire est la liste des indices dans laquelle on a enlevé deb I.E. une liste de longueur n-1.
Etapes suivantes :
On cherche le minimum m des distances provisoires dist reliant le
sommet deb aux sommets dont les numéros sont dans
afaire et on note jm le numéro du sommet réalisant ce minimum.
On supprime jm de la liste afaire.
On compare ensuite, pour tous les numéros des sommets restant afaire, la
longueur autredist des chemins qui passent par
jm à la valeur provisoire dist et si pour le sommet de numéro
k=afaire[j] le chemin qui passe par jm est plus court on modifie
dist[k] et on modifie sprec[k] qui vaut alors jm.
On recommence jusqu’a épuisement de la liste
afaire , c’est à dire que l’on fait cela n-1 fois.
Remarque
Attention aux indices !!!!
afaire est la liste des indices ou numéros des
sommets restant à traiter et il ne faut pas confondre le numéro des sommets
et les indices qu’ils ont dans la liste afaire i.e. ne pas confondre
k=afaire[j] avec j (si afaire=[2,0,1] le sommet 0 a pour
indice 1 dans afaire).
Dijkstra(A,deb):={
local j,k,n,na,dist,sprec,distaf,afaire,
m,jm,autredist,jma;
// initialisation
n:=size(A);
dist:=A[deb];
sprec:=[deb $n];
sprec[deb]:=-1;
n:=n-1;
//afaire liste des indices restant a faire
afaire:=suppress([j$(j=0..n)],deb);
na:=size(afaire)-1;
pour k de 0 jusque n-1 faire
//le sommet jm realise la dist m minimum de distaf
//jma est l'indice de m dans la liste distaf
//jm est l'indice de m dans la liste afaire
distaf:=[dist[afaire[j]]$(j=0..na)];
m:=min(distaf);
//jma indice du minimum m dans afaire
jma:=member(m,distaf)-1;
//jm indice du minimum m dans dist
jm:=afaire[jma];
//fin prematuree
si m==inf alors return dist,sprec; fsi;
afaire:=suppress(afaire,jma);
na:=na-1;
pour j de 0 jusque na faire
autredist:=m+A[jm,afaire[j]];
si autredist<dist[afaire[j]] alors
dist[afaire[j]]:=autredist;
sprec[afaire[j]]:=jm;
fsi;
fpour;
fpour;
retourne dist,sprec;
}:;
On tape :
M:=[[0,27,11,23],[27,0,14,1],[11,14,0,10],[23,1,10,0]]
Dijkstra(M,0)
On obtient (cf la section précédente) :
[0,22,11,21],[-1,3,0,2]
On tape :
A:=[[0,1,6,7],[1,0,4,3],[6,4,0,1],[7,3,1,0]]
Dijkstra(A,2)
On obtient :
[5,4,0,1],[1,2,-1,2]
cela veut dire par exemple pour aller de 2 à 0 la distance minimale est 5 et
le chemin est 2,1,0.
On tape :
B:=[[0,1,6,7],[1,0,4,2],[6,4,0,1],[7,2,1,0]]
Dijkstra(B,0)
On obtient :
[0,1,4,3],[-1,0,3,1]
cela veut dire par exemple pour aller de 0 à 2 la distance minimale est 4 et
le chemin est 0,1,3,2.
On tape en utilisant le programme précédent :
dijkstra2(A,deb,fin):={
local dist,sprec,long,chemin,j;
dist,sprec:=dijkstra(A,deb);
long:=dist[fin];
j:=sprec[fin];
chemin:=fin;
tantque j!=-1 faire
chemin:=j,chemin;
j:=sprec[j];
ftantque;
retourne long,[chemin];
}:;
ou bien en arrétant le programme dès que l’on a atteint le sommet fin, on tape :
dijkstra3(A,deb,fin):={
local j,k,n,na,dist,sprec,distaf,afaire,m,
jm,autred,jma,long,chemin;
n:=size(A);
//dist:=[inf$ n];dist[deb]:=0;
dist:=A[deb];
sprec:=[deb $n];
sprec[deb]:=-1;
n:=n-1;
//afaire liste des indices restant a faire
afaire:=suppress([j$(j=0..n)],deb);
na:=n-1;
pour k de 0 jusque n-1 faire
//minimum des distances dist[afaire[j]]
distaf:=[dist[afaire[j]]$(j=0..na)];
m:=min(distaf);
//jma indice du minimum m dans afaire
jma:=member(m,distaf)-1;
//jm indice du minimum m dans dist
jm:=afaire[jma];
si m==inf alors return dist,sprec; fsi;
si jm==fin alors
long:=dist[fin];
chemin:=jm;
j:=sprec[jm];
tantque j!=-1 faire
chemin:=j,chemin;
j:=sprec[j];
ftantque;
retourne long,[chemin];
fsi;
afaire:=suppress(afaire,jma);
na:=na-1;
pour j de 0 jusque na faire
autred:=m+A[jm,afaire[j]];
si autred<dist[afaire[j]] alors
dist[afaire[j]]:=autred;
sprec[afaire[j]]:=jm;
fsi;
fpour;
fpour;
}:;
On tape :
M:=[[0,27,11,23],[27,0,14,1],[11,14,0,10],[23,1,10,0]]
dijkstra3(M,0,1)
On obtient (cf la section précédente) :
22,[0,2,3,1]
dijkstra3(M,0,2)
On obtient (cf la section précédente) :
11,[0,2]
dijkstra3(M,0,3)
On obtient (cf la section précédente) :
21,[0,2,3]
On tape :
A:=[[0,1,6,7],[1,0,4,3],[6,4,0,1],[7,3,1,0]]
dijkstra2(A,2,0) ou dijkstra3(A,2,0)
On obtient : 5,[2,1,0]
On tape :
B:=[[0,1,6,7],[1,0,4,2],[6,4,0,1],[7,2,1,0]]
dijkstra2(B,0,2) ou dijkstra3(B,0,2)
On obtient :
4,[0,1,3,2]
On tape :
dijkstra2(B,2,0) ou dijkstra3(B,2,0)
On obtient :
4,[2,3,1,0]
Exemple avec une matrice créee aléatoirement
On tape :
MR:=randmatrix(5,5,’alea(50)+1’)
M:=MR+tran(MR)
pour j de 0 jusque 4 faire M[j,j]=<0; fpour;
M
On obtient :
[[0,47,91,57,60],[47,0,58,18,50],[91,58,0,22,74],
[57,18,22,0,70],[60,50,74,70,0]]
| ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ |
| ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ |
On tape :
Dijkstra(M,0)
On obtient :
[0,47,79,57,60],[-1,0,3,0,0]
On tape :
dijkstra2(M,0,2)
On obtient :
79,[0,3,2]