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 alcanza con recorrerlas una vez por cada nodo, es decir si el grafo tiene $V$ nodos, hacemos eso $V$ 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.

Ahora, hay un caso excepcional que puede ocurrir que es que hay 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.