OIA-Wiki

Encontrar la menor distancia entre un vértice (source, “origen” en inglés) y todos los demás, dadas aristas con longitudes. (Si bien pensar que la longitud de una arista es negativa no tiene sentido, se podría pensar como si la longitud fuera un costo, cuanto más larga más nos cuesta atravesar la arista, y longitud negativa significa que nos pagan por pasar por ahí, y queremos el camino de menor costo posible.)

La implementación de este algoritmo es súper sencilla.

El algoritmo consiste en hacer varias veces lo siguiente: recorrer todas las aristas. Si la arista $(u,v)$ de longitud $L$ es tal que la distancia que teníamos guardada desde source hasta el nodo $u$ más la longitud de la arista $L$, es menor a la distancia que teníamos guardada hasta el nodo $v$, actualizamos la información de la distancia hasta el nodo $v$ como la suma mencionada.

Cuántas veces tenemos que recorrer las aristas? La idea fuerte del algoritmo es que si el grafo tiene $V$ nodos, alcanza con recorrer las aristas $V-1$ veces. Se ve entonces que la complejidad del algoritmo es $\large O(V.E)$ donde $V$ es la cantidad de vértices y $E$ la de aristas. La demostración de esta idea puede verse en wikipedia (Bellman-Ford), prueba por inducción que después de recorrer las aristas $i$ veces, en cada nodo hay guardada la mejor distancia desde el nodo source con a lo sumo $i$ aristas (al principio con $0$ aristas, la única información es que hasta el mismo nodo source la menor distancia vale $0$). Como, si no hay ciclos negativos, no vamos a pasar más de una vez por ningún vertice, en un camino hay a lo sumo $V-1$ aristas.

Ahora, hay un caso excepcional que puede ocurrir que es que haya un ciclo de suma negativa. Si por ejemplo tuvieramos las aristas $(u, v), (v, w), (w, u)$ de pesos $10, -5, -12$ respectivamente, al llegar al nodo $u$ con cualquier distancia nos conviene ir al nodo $v$, luego al $w$ y volver al $u$, habiendo reducido la distancia anterior. Y nos conviene hacer eso indefinidamente.

Lo que afirma el algoritmo es que si luego de recorrer todas las aritas $V$ veces, hacemos esto una vez más y encontramos una arista $(u, v)$ que hace que la suma de la distancia actual hasta $u$ más la longitud de la arista nos achique la distancia obtenida hasta el nodo $v$, entonces hay un ciclo negativo, y el problema no tiene sentido, ya que no hay una distancia mínimo hasta los nodos que estén en el ciclo negativo pues podemos achicarla cuanto queramos.

Algo que podemos hacer para reconstruir caminos, que sirve en general en muchos algoritmos de grafos, es, al actualizar la distancia, guardar esa actualización en un vector “antecesor”, que significa que para llegar al nodo $v$ nos conviene llegar desde el $u$, por ejemplo.

Y por último, algo que no mejora la eficiencia en el peor caso pero no es muy complejo de agregar, es la siguiente idea: si recorro todas las aristas, y no actualizo ninguna información, en el siguiente va a pasar exactamente lo mismo. Entonces si una vez no actualizé nada, puedo cortar el algoritmo aunque haya hecho el procedimiento menos de $V$ veces.

#define forn(i,n) for(int i=0;i<(int)(n); i++)
 
struct arista{
	int u, v, longitud;
};
 
vector<int> bellmanFord(vector<arista> grafo, int source, int cantidadNodos){
	int INF=2e9;
	vector<int> distancia(cantidadNodos, INF);
	vector<int> antecesor(cantidadNodos, -1);
	distancia[source]=0;
	forn(_, cantidadNodos-1){
		bool modifico=false;
		forn(j, grafo.size()){
			arista actual = grafo[j];
			if( distancia[actual.u] + actual.longitud < distancia[actual.v] ){
				distancia[actual.v] = distancia[actual.u] + actual.longitud;
				antecesor[actual.v]=actual.u;
				modifico=true;
			}
		}
		if(!modifico){
			break;
		}
	}
 
	forn(j, grafo.size()){
		arista actual = grafo[j];
		if( distancia[actual.u] + actual.longitud < distancia[actual.v] ){
			cout<<"ERROR, CICLO NEGATIVO"<<endl;
		}
	}
	return distancia;
}