4.3.3. Problemas de caminos mínimos.

Algoritmo de Dijkstra

var

i: integer;

begin

for i:= 2 to N do begin

S[i]:= false;

D[i]:= C[1, i];

P[i]:= 1;

end;

for i:= 1 to N-1 do begin

v:= vértice con D[v] mínimo y S[v]=false;

S[v]:= true;

for cada nodo w adyacente a v do

if S[w]=false then

if D[v]+C[v, w]<D[w] then begin

D[w]:= D[v]+C[v, w];

P[w]:= v;

end;

end;

end;

S: array [2..N] of boolean;

{ Nodos conocidos }

D: array [2..N] of integer;

{ Costos de los caminos }

P: array [2..N] of integer;

{ Camino de 1 a v }

C: array [1..N, 1..N] of integer;

{ Matriz de costos de todas

las aristas }

procedure ImprimeCamino (v: integer);

begin

if v<ɭ then

ImprimirCamino(P[v]);

write(v);

end;

Diapositiva anterior Diapositiva siguiente Ir a la primera diapositiva Ver versión gráfica