Programmation de l’algorithme de Dijkstra avec Matlab

Programmation de l’algorithme de Dijkstra avec Matlab

L’objectif de ce tutoriel est de programmer l’algorithme de plus court chemin de Dijkstra.

Description de l’algorithme de Dijkstra (Wikipédia)

En théorie des graphes, l’algorithme de Dijkstra (prononcer [dɛjkstra]) sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer le plus court chemin pour se rendre d’une ville à une autre connaissant le réseau routier d’une région. Il s’applique à un graphe connexe dont le poids lié aux arêtes est positif ou nul.L’algorithme porte le nom de son inventeur, l’informaticien néerlandais Edsger Dijkstra et a été publié en 1959.

L’idée de base de l’algorithme est d’explorer le graphe à partir de la source et des sommets marqués pris par ordre croissant de leur distance à s. Au départ la source sreçoit comme étiquette (permanente) et les autres sommets du graphe une étiquette (temporaire).
À chaque itération, l’étiquette d’un sommet 
est sa plus courte distance depuis la source le long d’un chemin dont tous les sommets internes (interne = les sommets du chemin sauf ses deux extrémités, ici et v) sont marqués. L’algorithme choisit le sommet non-marqué de plus petite étiquette, le marque et met à jour les étiquettes de tous les voisins inon-marqués de :      d[i] <– min{d[i], d[x]+Iix}

Afin de connaître les chemins calculés, si d[i]   <–  d[x]+Iix

 On note que le prédécesseur de sur le plus court chemin calculé est x. L’algorithme se termine lorsque tous les sommets sont marqués.

Programmation de l’algorithme :

Le programme va être découpé on plusieurs parties : Les données sur le graphe vont être mentionnées dans un fichier txt comme sur l’image :

1)    le code de la fonction qui va lire le fichier et affiche la matrice d’adjacence. Elle a comme retour la matrice A et le nombre de sommets tg .


function [A,tg]=lireFichier(fid)
 a =fgetl(fid);
 b= str2num(fgetl(fid));
 c= str2num(fgetl(fid));
 tg=b;
 for k= 1:b
  for j=1:b
   A(k,j)=-1;
  end
 end
 for i=1:c
  d=str2num(fgetl(fid)) ;
  A(d(1),d(2))=d(3);
 end
end

2)    la  fonction qui renvoie la valeur initiale de l’étiquette du sommet x (0 si x = s, sinon l’infini). Le sommet s est la source à partir de la quelle on calcule les plus courts chemins.

function va=valetiqinit(s,b)
 if s==b
  va=0;
 else
  va=1000;
 end
end

3)    Cette fonction  demande à l’utilisateur la source à utiliser dans l’algorithme de Dijkstra, intitialise les tableaux des prédécesseurs (prédécesseur de x = x) et des sommets marqués et utilise le résultat de la fonction valetiqinit pour initialiser les étiquettes.

Cette fonction retourne trois  Tableaux E(i) pour la valeur des Etiquettes M(i) qui prend soit vrai ou faux P(i) pour les prédécesseurs.

function [E,M,P]=initdij(s,tg)
 for i=1:tg
  E(i)=valetiqinit(s,i);
  M(i)=false;
  P(i)=i;
 end
end

4)    la fonction qui recherche le prochain sommet à marquer : cette fonction prend les trois tableaux précédents et la taille du graphe pour donner le numéro du prochain sommet à marquer.

function p=prochain(s,e,m,tg)
 k=1000;
 proch=s;
 for i=1:tg
  if (~m(i)) & (e(i)
   k=e(i);
   proch=i;
  end
 end
 p=proch;
end

5) la fonction qui permet de relaxer les voisins non marqués du sommet qui vient d’être marqué.

function [e,m,p]=relaxer(A,e,m,n,p,tg)
 m(n)=true;
 for i=1:tg
  if (A(n,i)~=-1)& (~m(i))
   re=relax(e(n),e(i),A(n,i));
   if re
    p(i)=n;
   end
  end
 end
end
function r=relax(a,b,c)
 if (c~=-1)& (a+c  r=a+c;
 else
  r=b;
 end
end

6)    la fonction qui calcule et donne le plus court chemin sur le graphe à partir de s.

function [e,m,p]=courts(A,s,tg)
 [e,m,p]=initdij(s,tg);
 n=s;
 for i=1:tg
  [e,m,p]=relaxer(A,e,m,n,p,tg);
  n=prochain(s,e,m,tg);
 end
end

7)    la fonction qui relie la lecture du fichier où il y a les données  et le programme qui va faire la relaxation et le calcule du chemin le plus court.

function [e,m,p]=dijkstra(fid,s)
  [A,tg]=lireFichier(fid);
  [e,m,p]=courts(A,s,tg);
end

C’est une fonction qui reçoit la source et le fichier et qui donne les trois tableaux :

e(i) : le plus courts chemin entre s et sommet i
p(i) : le prédécesseur de i

 Teste du programme :

Exemple de graphe :

Résultat :

e(2)=12 et p(2)=4
e(3)=11 et p(3)=5
e(4)=9 et p(4)=5
e(5)=4 et p(5)=1

Faites-moi part de vos remarques s’il y a des erreurs.