7/18/2019 Dijk Stra

http://slidepdf.com/reader/full/dijk-stra-569715e167b8a 1/2

Algoritmul lui Dijkstra determina câte un drum de cost minim de la vârful sursa x0,la fiecare dintre celelalte vârfuri ale grafului.Initial, singurul vârf pentru care drumul de cost minim este deja cunoscut este numai vârful sursa x0.La fiecare pas se va selecta un vârf, care nu a mai fost selectat si care se aflala distanta minima de multimea vârfurilor selectate (cele pentru care drumul de cost minim este deja determinat).Distanta de la multimea vârfurilor deja selectate (sa o notam M) la un vârf oarecare yeste egala cu costul drumului de cost minim de la vârful sursa x0 la y, drum care trece numai prin vârfuri din multimea M.Dupa selectarea vârfului situat la distanta minima de M (fie acesta y), toate distantele de la M la vârfurile neselectate trebuie actualizate.Mai exact, sa notam d[z] distanta de la vârful neselectat z la multimea M, înainte de selectarea vârfului y.Prin includerea vârfului y în multimea M este posibil sa obtinem un drum de cost mai mic, daca distanta d[z] este mai mare decât distanta pâna la vârful y (d[y]) +costularcului (y, z), adica d[z]>d[y]+c[y][z]. În acest caz, distanta de la multimea M la vârful z trebuie actualizata.Pentru a putea reconstitui si drumurile de cost minim, vom retine pentru fiecare vârf ydin graf (exceptând vârful x0) vârful care îl preceda pe drumul de cost minim de x0la y.În animatie, observati ca vârfurile incidente cu arcele rosii apartin multimii M (au fost selectate) iar extremitatile finale ale arcelor verzi sunt vârfurile catre care s-a facut actualizarea si care sunt luate în calcul pentru selectare la urmato

rul pas.pascal:procedure dijkstra(var x0: integer)

 var i, j, min, k, ok: integer;

 var viz, d, tata: Array[1..NMAX] of integer;

 begin

 for i := 1 to n do begin

  d[i] := C[x0][i];

  tata[i] := x0;

  viz[i] := 0;

 end;

 tata[x0] := 0;

 viz[x0] := 1; ok := 1;

 while (ok=1) do begin

  min := INFINIT;

  for i := 1 to n do 

if (viz[i]=0) and (min>d[i]) then begin

  min := d[i];

7/18/2019 Dijk Stra

http://slidepdf.com/reader/full/dijk-stra-569715e167b8a 2/2

  k := i;

  end;

  if min <> INFINIT then begin

  viz[k] := 1;

  for i := 1 to n do 

if(viz[i]=0) and (d[i]>d[k]+C[k][i])then begin  d[i] := d[k]+C[k][i];

  tata[i] := k;

  end;

  end

  else ok := 0;

 end;

end;