OIA-Wiki

Este algoritmo permite conocer la menor distancia entre todo par de nodos, en un grafo con aristas con longitudes. El único requisito para que este algoritmo tenga sentido es que no haya ciclos negativos, ya que si no, no existe una “mínima distancia” entre dos nodos, porque simplemente vamos al ciclo y lo recorremos todas las veces que queramos, reduciendo así la distancia del recorrido.

El código es muuuy fácil de implementar.

Vamos a tener un vector de dos dimensiones que en la posición $j$ del vector $i$ tenga la distancia entre el nodo $i$ y el $j$. Inicialmente todas estas distancias valen “infinito” (ya que buscaremos actualizar la información con valores menores), excepto las distancias entre nodos unidos por una arista, donde la distancia vale la longitud de la arista.

Este algoritmo es uno de los más conocidos de programación dinámica. Se puede (y se recomienda) leer sobre eso acá, aunque no es necesario para entender el algoritmo. Lo que hace es, en el i-ésimo paso, haber mirado todos los caminos que utilizan en el medio a los primeros $i$ nodos a lo sumo una vez. Luego de $V$ pasos, habremos mirado los caminos que utilizan cualquier nodo en el medio, habiendo mirado todos. La demostración queda como ejercicio para quien quiera pensarla, y también se puede leer acá.

Va el código:

#define forn(i,n) for(int i=0;i<int(n); i++)
 
struct arista{
    int u, v, longitud;
};
 
vector< vector<int> > floydWarshall(vector<arista>& grafo, int V){
    const int INF = 2e9;
    vector< vector<int> > distancia(V, vector<int>(V, INF));
    forn(i, grafo.size()){
        arista a = grafo[i];
        distancia[a.u][a.v]=a.longitud;
        // Si el grafo no es dirigido, es decir que puedo ir de v a u por esta misma arista, agrego:
        // distancia[a.v][a.u]=a.longitud;
    }
    forn(k, V){
        forn(i, V){
            forn(j, V){
                distancia[i][j] = min(distancia[i][j], distancia[i][k] + distancia[k][j]);
                // Si el grafo no es dirigido, hago:
                // distancia[j][i]=distancia[i][j];
            }
        }
    }
    forn(i, V){
        if(distancia[i][i]<0){
            cout<<"ERROR, CICLO NEGATIVO"<<endl;
        }
    }
    return distancia;
}

Notar que la detección de un ciclo negativo se hace mirando $distancia[i][i]$. Si un nodo está en un ciclo negativo, entonces el algoritmo va a guardar como longitud mínima el camino desde $i$, pasando por el ciclo negativo, y volviendo a $i$, entonces hay un ciclo negativo si y sólo si hay algún nodo con $distancia[i][i]<0$