Algoritmo de Floyd

Este algoritmo calcula el camino mínimo entre todo par de vértices de un digrafo pesado. Utiliza programación dinámica y se basa en la sigiente idea:

Si $D^{0} = L$ y calculamos $L^{1}$ como $d_{i j}^{1} = m í n (d_{i j}^{0}, d_{i 1}^{0} + d_{1 j}^{0})$ , donde $d_{i j}^{1}$ es la longitud de un camino mínimo de $v_{i}$ a $v_{j}$ con vértices intermedio $v_{1}$ o directo.
Si calculamos $D^{k}$ a partir de $D^{k - 1}$ como $d_{i j}^{k} = m í n (d_{i j}^{k - 1}, d_{i k}^{k - 1} + d_{k j}^{k - 1})$ donde $d_{i j}^{k}$ es la longitud de un camino mínimo de $v_{i}$ a $v_{j}$ cuyos vértices intermedios están en ${v_{i}, \dots, v_{k}}$ .
$D = D^{n}$ .

Damos por hecho que no existen circuitos de longitud negativa.

El pseudocodigo del algoritmo podria escribirse:

Floyd(G)
	D = L;
	for (k desde 1 a n) do:
		for (i desde 1 a n) do:
			for (j desde 1 a n) do:
				d[i][j] = mín(d[i][j], d[i][k] + d[k][j]);
			end for;
		end for;
	end for;
	return D;

Donde $G = (V, X)$ es un digrafo de $n$ vertices, y $D$ es una matriz de distancias de $G$ .

Este algoritmo tiene complejidad $O (n^{3})$ , bastante malo.