Algoritmo de Bellman-Ford

El algoritmo de Ford para camino mínimo funciona exclusivamente en dígrafos que pueden tener distancias negativas, pero no debe existir un loop de longitud negativa. De ser este el caso, podriamos iterar infinitamente por dicho loop, minimizando la distancia y el programa nunca terminaria.

Lo primero que haremos sera tener una lista en la que guardaremos todas las distancias de cada nodo con $v$ , el nodo ingresado. La lista empezará con todas las posiciones en $\infty$ , salvo por la posicion correspondiente con $v$ , que sera $0$ .

Primero veremos todos los vecinos de $v$ , y actualizaremos la lista de distancias con los nodos respectivos. Luego pasamos al siguiente elemento de la lista, y donde pueden suceder dos cosas: o bien su distancia es distinta de $\infty$ , o bien sigue siendo $\infty$ . El primer caso significaria que ya fue alcanzado por un nodo anterior, es decir, su posible distancia minima a $v$ ya esta calculada. En ese caso, vemos a los vecinos de ese nodo y actualizamos la tabla si encontramos alguna distancia menor a la guardada. En el segundo caso, significa que ese nodo todavia no fue alcanzado desde $v$ , por lo que lo ignoramos y pasamos al siguiente.

Esto lo repetimos una cantidad de veces igual a $| V | - 1$ . Cada iteración las distancias se van a ir corrigiendo, teniendo en cuenta las distancias negativas y las distintas formas de llegar a cada nodo. Siempre y cuando no haya loops de longitud negativa, el algoritmo al final completa la lista con la mínima distancia de cada nodo con $v$ .

Ford(G, v):
	for (u perteneciente a V) do:
		distancias(u) = infinity;
	end for;
	distancias(v) = 0;
	for ((|V| - 1) veces) do:
		for (e perteneciente a E) do: // e = (u,w)
			distancias(w) = min(distancias(w), distancias(u) + l(u,w));
		end for;
	end for;
	return distancias;

Este algoritmo tiene una complejidad de $O (m * n)$ , ya que todas las aristas son visitadas una cantidad de nodos veces.