4.3.3. Problemas de caminos mínimos.

Algoritmo de Floyd

procedure Floyd (C: array [1..N, 1..N] of integer);

var

k, i, j: integer;

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

begin

for i:= 1 to N do

for j:= 1 to N do

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

for k:= 1 to N do { k es el pivote }

for i:= 1 to N do

for j:= 1 to N do

D[i, j]:= min (D[i, j], D[i, k] + D[k, j]);

end;

• Tenemos los costos de los caminos mínimos, ¿cómo saber cuales son los caminos?

• Igual que en Dijkstra, una matriz P de NxN almacena el camino. P[i, j]=0 si el camino es directo. En otro caso, el camino de i a j pasa por P[i, j].

  if D[i, k] + D[k, j] < D[i, j] then
  
  D[i, j]:= D[i, k] + D[k, j];
  P[i, j]:= k;

1

2

3

2

3

2

5

8

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica