Camino más corto entre nodos

En este capítulo veremos cómo hallar el camino más corto entre dos nodos en un grafo ponderado (si el grafo no es ponderado es suficiente con realizar un BFS). Para ello nos serviremos de distintos algoritmos en función de cuál sea nuestro objetivo y el tipo de grafo con el que trabajamos.

Dijkstra

La manera más eficiente para encontrar la distancia mínima entre dos vértices de un grafo con pesos no negativos es usando el algoritmo de Dijkstra. La idea principal del algoritmo es muy sencilla: Iremos construyendo un grafo F, inicialmente formado únicamente por el nodo origen. En cada paso miraremos todos los nodos a los que podamos llegar directamente desde F, es decir aquellos que compartan arista con un nodo de F, y añadiremos el nodo cuya distancia al origen sea mínima (con la arista que minimice dicha distancia). Pararemos el algoritmo en el momento en que el vértice a incluir a F sea el nodo destino.

Nótese que en cada iteración, al incluir un nodo (v) a F podemos estar seguros que lo estamos tomando utilizando el menor camino del origen al nodo v.  De existir otro camino, este debería pasar por alguno de los otros nodos a los que podemos llegar directamente desde F, los cuales están a mayor o igual distancia del origen que el nodo v, por construcción. Dado que los pesos son no negativos, cualquier camino que pase por alguno de estos nodos para llegar a v no puede tener una distancia menor a la que estábamos considerando inicialmente. De modo que al final del algoritmo habremos hallado la distancia mínima entre el origen y el destino.

Veamos un ejemplo: consideremos el siguiente grafo:

Usaremos el algoritmo de dijkstra para encontrar el camino más rápido entre los nodos 1 y 6. A continuación figuran los pasos del algoritmo:

Vemos que la distancia mínima entre 1 y 6 es 7. Nótese que a cada paso añadimos los nuevos arcos teniendo en cuenta la distancia al nodo origen. 

Observaciones:

• En este caso el algoritmo ha dado lugar a un camino, pero en general puede dar lugar a cualquier tipo de árbol.
• En este caso el grafo no era dirigido, pero el algoritmo funciona también para grafos dirigidos.
• El algoritmo solo funciona si todos los pesos son no negativos.
• La complejidad del algoritmo es de $\mathcal{O}(|E| + |V| · log(|V|))$ aunque nuestra implementación será de $\mathcal{O}(|E| · log(|V|))$ 
• Si todos los pesos son iguales, es mejor utilizar un BFS.
• Al usar el algoritmo de Dijkstra realmente estaremos calculando la distancia mínima ente u y cualquier nodo que este más cerca que v. Es decir, con la misma complejidad podemos hallar la mínima distancia de un nodo a todos los demás. 

 

A nivel de código es muy similar al del BFS, salvo que utilizamos una cola de prioridad, de modo que en todo momento sepamos el nodo que está a distancia mínima del nodo origen. La cola será de parejas y guardaremos el peso del arco y el nodo que conecta . Es importante mantener este orden, pues queremos comparar primero por peso; además, dado que la cola ordena de mayor a menor, guardaremos los pesos negativos:

// Dados un grafo G, sus pesos W, el número de nodos n, y dos nodos s, t devuelve la mínima
// distancia entre s y t
int dijkstra (vvi& G, vvi& W, int n, int s, int t){
    vector <bool> vis(n, false); //nodos visitados, inicialmente ninguno
    priority_queue <ii> Q; //cola de prioridad
    Q.push({-0,s}); //introducimos el nodo origen (a distancia 0 de él mismo)

    while (not Q.empty()){
        ii arc = Q.top() //arco con menor peso desde F hasta G\F 
        Q.pop(); //lo quitamos de la cola

        int v = arc.second; //vértice de Q a menor distancia del nodo origen
        int p = arc.first; //distancia entre el nodo origen y v
        
        if (v == t) return -p; //si es el nodo destino hemos acabado

        if (not vis[v]){ //si no lo hemos visitado
            vis[v] = true;
            for (int i = 0; i < G[v].size(); ++i){ //miramos sus vecinos
                int u = G[v][i];
                int w = W[v][i];

                Q.push({p-w, u}); // añadimos los vecinos con la distancia a s
            }
        }
    }

    return inf; // no hay caminos entre s y t
}

Observación: Se puede hacer más eficiente si solo añadimos a la cola los nodos no visitados.

Bellman-Ford

Supongamos ahora que estamos trabajando con un grafo dirigido con pesos negativos, en este caso el algoritmo de Dijkstra podría darnos un resultado erróneo. Para resolver el mismo problema que antes: hallar el mínimo camino entre dos nodos de un grafo ponderado, pero esta vez admitiendo pesos negativos, podemos utilizar el algoritmo de Bellman-Ford. 

Inicialmente, la distancia del nodo origen a uno cualquiera es infinito, salvo la distancia al propio nodo origen que será 0, e iteración tras iteración mejoraremos las distancias. La idea detrás del algoritmo es considerar los caminos saliendo del nodo origen y compuestos por dos nodos, luego los compuestos por tres, y así sucesivamente hasta llegar a caminos formados por n nodos, siendo n el número de vértices. Nótese que puesto que hemos asumido que no hay ciclos negativos, no es óptimo recorrer ciclos, y por ende, no es necesario mirar caminos de distancia mayor o igual a n, pues en ese caso estaríamos repitiendo algún nodo, es decir, estaríamos considerando únicamente caminos que contienen ciclos. 

Para lograr nuestro objetivo realizaremos n - 1 iteraciones, en cada una de las cuales consideraremos todos los arcos (u -> v, w). Si tomando este arco podemos mejorar la distancia del nodo origen al nodo v, consideraremos este arco. Dicho de otro modo, si la distancia del origen al nodo u + w es menor que la distancia del origen al nodo v, actualizaremos la distancia del origen al nodo v. De este modo tras la iteración i-ésima la distancia del nodo origen a uno cualquiera será la menor distancia a la que podemos llegar a ese nodo desde el origen usando solo caminos de como mucho i+1 nodos. 

Nótese que en realidad en la primera iteración, dependiendo del orden en que cojamos los arcos y del grafo con el que trabajamos podemos llegar a considerar caminos formados por más de un nodo, de hecho hasta n-1 nodos. Sin embargo, no podemos asegurar haber considerado todos los caminos formados por n-1 vértices hasta no haber hecho n-1 iteraciones. Acabadas todas las iteraciones habremos dado con la distancia mínima con que podemos llegar del nodo origen al final con un camino de n nodos o menos, y por ende, con la solución del problema.

A continuación veremos un ejemplo, consideramos el siguiente grafo:

Queremos hallar la distancia mínima desde el vértice 2 hasta el 1. Para ello usaremos el algoritmo de Bellman-Ford. A continuación figura una tabla con las iteraciones, los arcos que vamos considerando y las distancias actualizadas en cada momento:

Vemos que la mínima distancia entre 2 y 1 es -2. De haber aplicado el algoritmo de Dijkstra, nos hubiese salido 2, lo cuál es obviamente erróneo. 

Observaciones:

• En este caso no han sido necesarias n-1 iteraciones para hallar la respuesta, esto sucede porque en la primera iteración ya se nos ha formado un camino de 3 nodos 2 -> 4 -> 5. Pero si el 2 -> 4 fuese el último arco que visitamos en vez del tercero, entonces sí hubiesen sido necesarias n-1 iteraciones (es decir las 4). Es por eso que hacemos n-1 iteraciones, para asegurarnos que cojamos como cojamos los arcos, obtendremos la respuesta correcta.
• Al final, no solo obtenemos la mínima distancia del nodo origen al destino, sino la mínima distancia desde el nodo origen hasta cualquier otro nodo.
• El problema no tiene sentido con grafos no dirigidos, pues si hay un arco negativo podemos tomarlo en uno y otro sentido infinitas veces, mejorando constantemente el resultado y, de no haber pesos negativos, usaríamos el algoritmo de Dijkstra.
• La complejidad del algoritmo es de $\mathcal{O}(|E| · |V|)$ 
• Los nodos a los que no se puede llegar desde el nodo origen quedarán a distancia infinita.

Una posible implementación del algoritmo sería la siguiente:

 

// Dados el número de nodos del grafo (n), el número de arcos (m), un nodo origen (s), un
// nodo destino (t) y el conjunto de aristas (edges) donde edge[i] = {nodo donde empieza el 
// arco, nodo donde termina, peso}, devuelve la mínima distancia para ir desde s hasta t.
int Bellman_Ford (vvi& edges, int n, int m, int s, int t){
    vi d(n, inf); // vector de distancias, inicialmente inf (un número grande como 1e9)

    d[s] = 0; // la distancia al nodo origen es 0
    for (int i = 0; i < n-1; ++i){ // hacemos n-1 iteraciones
        for (int j = 0; j < m; ++j){ // en cada una miramos todos los arcos
        int v = edges[j][0];
        int u = edges[j][1];
        int w = edges[j][2];

        d[u] = min(d[u], d[v] + w); // actualizamos distancia (si es necesario)
        }
    }
    
    return d[t]; // devolvemos la distancia de s a t
}

Floyd-Warshall

Supongamos ahora que tenemos que calcular la mínima distancia entre todos los pares de vértices de un grafo ponderado. Lo podríamos hacer en $\mathcal{O}(|V|· (|E| + |V| · log(|V|))$  realizando un Dijkstra por cada nodo. Pero si los pesos son negativos, no podríamos usar este método, tendríamos que hacerlo en $\mathcal{O}(|E| · |V|^2)$ realizando n veces el algoritmo de Bellman-Ford, una por cada vértice. Sin embargo, se puede hacer aún más rápido utilizando el algoritmo de Floyd-Warshall, el cual, al igual que Bellman-Ford admite pesos negativos, siempre y cuando no haya ciclos negativos.

La idea del algoritmo es parecida a la de Bellman-Ford. Vamos a realizar n iteraciones, en cada iteración estaremos considerando los caminos óptimos que tienen como nodos intermedios aquellos con índice menor a i (si los vértices están numerados de 0 a n-1; si estuviesen numerados de 1 a n entonces menor o igual a i). De modo que tras n iteraciones habremos considerado los caminos óptimos que incluyen cualquier nodo, es decir, los caminos óptimos en general. 

En este caso trabajaremos por comodidad con un grafo dado como matriz de adyacencia. Tendremos otra matriz (dist) de n filas y n columnas de modo que en la casilla dist[i][j] guardaremos la mínima distancia del nodo i al j. Al igual que en el algoritmo de Bellman-Ford inicialmente el valor de todas las distancias es infinito, a excepción de aquellas en que exista un arco directo de i a j, en cuyo caso el valor de dist[i][j] será el peso del arco. Además por convención dist[i][i] = 0 (aunque esto lo podemos declarar al final del algoritmo). Realizaremos n iteraciones, en cada una de las cuales consideraremos todas las parejas de nodos, de modo que en la iteración k-ésima si vemos que pasar por el vértice k en el recorrido de i a j es óptimo, actualizaremos el valor de la distancia de i a j. Dicho de otro modo, si dist[i][k] + dist[k][j] es menor que dist[i][j] actualizamos esta última. Al haber considerado como “nodo intermedio” todos los n nodos del grafo habremos acabado.

Veamos el siguiente ejemplo, dado el grafo:

Queremos hallar la mínima distancia entre cada par de nodos.

Iteración 0: Inicialización de las distancias

Iteración 1: Consideramos caminos que tengan 1 como nodo intermedio

Iteración 2: consideramos caminos que tengan 1 y/o 2 como nodos intermedios

Iteración 3: caminos con nodos intermedios que incluyan vértices 1, 2, 3

Iteración 4: caminos con nodos intermedios que incluyan vértices 1, 2, 3, 4 

Iteración 5: caminos con nodos intermedios que incluyan vértices 1, 2, 3, 4, 5

Al final obtenemos la mínima distancia entre cada par de nodos.

Observaciones:

• En este caso solo con 4 iteraciones ya teníamos la respuesta correcta. Esto se debe a que no hay caminos que tengan 5 como nodo intermedio, y por ende, no habrá mejoras al considerarlo como posible nodo intermedio. Sin embargo, en general se requieren n iteraciones, dado que puede haber caminos óptimos que tengan como alguno de sus nodos intermedios el de mayor índice.
• La complejidad del algoritmo es de $\mathcal{O}(|V|^3)$ 
• Las parejas de nodos entre las que no existe un camino quedan a distancia infinita.

 

A continuación vemos una posible implementación del algoritmo:

// Dados el número de nodos del grafo (n), el grafo (G) como matriz de adyacencia y una 
// matriz dist, guarda en dist la distancia mínima entre cada par de nodos, de modo que 
// dist[i][j] es la distancia mínima para ir del nodo i al j
void Floyd_Warshall (int n, vvi& G, vvi& dist){
    dist = G;
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < n; ++j){
            if (i != j and dist[i][j] == 0) dist[i][j] = inf; 
            //las parejas de nodos sin arco están a distancia inf (p.e. 1e9)
        }
    }

    for (int k = 0; k < n; ++k){ //por cada nodo intermedio k
        for (int i = 0; i < n; ++i){
            for (int j = 0; j < n; ++j){ //miramos todas las parejas de nodos
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                //Si pasando por k mejoramos el resultado, lo actualizamos
            }
        }
    }
}