4.3.3. Problemas de caminos mínimos.

procedure Camino (i, j: integer);

var

k: integer;

begin

k:= P[i, j];

if k <> 0 then begin

Camino (i, k);

Write (k);

Camino (k, j);

end;

end;

• ¿Cuál es el orden de complejidad del algoritmo de Floyd?

• Cierre transitivo.

Dada una matriz de adyacencia M de un grafo dirigido, obtener una matriz A de valores booleanos en la que A[i, j] indica si existe o no un camino de i a j.

Algoritmo de Warshall

• Es parecido al algoritmo de Floyd. En lugar de enteros (costos) trabajamos con booleanos (existe arista o no).

• Inicialmente A=M. En cada paso k: A[i, j]:= A[i, j] or (A[i, k] and A[k, j]).

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica