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:

floyd.cpp

#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 = 1000000000;
    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]);
            }
        }
    }
    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$

¿Qué ocurre cuando, además de computar la distancia mínima para todo par de nodos, se desea poder obtener un camino mínimo para cualquier par dado?

Hay varias formas posibles. Explicamos a continuación una de las más simples.

La idea consiste en guardar una matriz adicional, de modo que $siguiente[i][j]$ indique cuál es el siguiente nodo luego del comienzo $i$, que se debe utilizar en el camino óptimo para ir desde $i$ hasta $j$. Es decir, sería el segundo nodo del camino, donde el primero es el propio $i$.

Inicialmente, recordemos que en la inicialización de la matriz del algoritmo de Floyd, únicamente tenemos considerados los caminos que no utilizan ningún nodo intermedio, es decir, aquellos caminos directos que llegan a destino usando una única arista a lo sumo. Por lo tanto, inicialmente tendremos $siguiente[i][j] = j$ para todos los pares $i,j$.

Además de esta inicialización, el único cambio que realizamos es que, dentro del for principal, junto con la actualización de la distancia, se actualiza quién es el siguiente al encontrar un mejor camino.

El algoritmo queda entonces:

floyd_con_caminos.cpp

    // Aqui va la inicializacion de distancias, exactamente igual que antes.
    vector< vector<int> > siguiente(V, vector<int>(V));
    forn(i,V)
    forn(j,V)
        siguiente[i][j] = j;
    forn(k, V) {
        forn(i, V) {
            forn(j, V) {
                int nueva = distancia[i][k] + distancia[k][j];
                if (nueva < distancia[i][j]) {
                    distancia[i][j] = nueva;
                    siguiente[i][j] = siguiente[i][k];
                }
            }
        }
    }

¿De qué nos sirve tener esta tabla adicional $siguiente$? Gracias a ella, podemos reconstruir un camino óptimo desde $i$ hasta $j$ fácilmente: iniciamos en $x=j$, y luego en cada paso nos movemos desde el nodo actual $x$ hasta $siguiente[x][j]$, parando al llegar a $j$. La secuencia de nodos utilizada forma el camino óptimo.

print_camino.cpp

    // Muestra todos los nodos del camino optimo de i hasta j
    int x = i;
    cout << i << "\n";
    while (x != j) {
        x = siguiente[x][j];
        cout << x << "\n";
    }