Algoritmo de Johnson

El algoritmo de Johnson es una forma de encontrar el camino más corto entre todos los pares de vértices de un grafo dirigido disperso. Permite que las aristas tengan pesos negativos, si bien no permite ciclos de peso negativo. Funciona utilizando el algoritmo de Bellman-Ford para hacer una transformación en el grafo inicial que elimina todas las aristas de peso negativo, permitiendo por tanto usar el algoritmo de Dijkstra en el grafo transformado. Su nombre viene de Donald B. Johnson, quien fuera el primero en publicar la técnica en 1977.

Descripción del algoritmo

El algoritmo de Johnson consiste en los siguientes pasos:

Primero se añade un nuevo nodo q al grafo, conectado a cada uno de los nodos del grafo por una arista de peso cero.
En segundo lugar, se utiliza el algoritmo de Bellman-Ford, empezando por el nuevo vértice q, para determinara para cada vértice v el peso mínimo h(v) del camino de q a v. Si en este paso se detecta un ciclo negativo, el algoritmo concluye.
Seguidamente, a las aristas del grafo original se les cambia el peso usando los valores calculados por el algoritmo de Bellman-Ford: una arista de u a v con tamaño w(u, v), da el nuevo tamaño w(u, v) + h(u) – h(v)
Por último, para cada nodo s se usa el algoritmo de Dijkstra para determinar el camino más corto entre s y los otros nodos, usando el grafo con pesos modificados.

En el grafo con pesos modificados, todos los caminos entre un par de nodos s y t tienen la misma cantidad h(s) – h(t) añadida a cada uno de ellos, así que un camino que sea el más corto en el grafo original también es el camino más corto en el grafo modificado y viceversa. Sin embargo, debido al modo en el que los valores h(v) son computados, todos los pesos modificados de las aristas son no negativos, asegurando entonces la optimalidad de los caminos encontrados por el algoritmo de Dijkstra. Las distancias en el grafo original pueden ser calculadas a partir de las distancias calculadas por el algoritmo de Dijkstra en el grafo modificado invirtiendo la transformación realizada en el grafo.

Análisis de la complejidad

La complejidad temporal de este algoritmo, usando montículos de Fibonacci en la implementación del algoritmo de Dijkstra, es de O(V²log V + VE): el algoritmo usa un tiempo de O(VE) para la fase Bellman-Ford del algoritmo, y O(V log V + E) para cada una de las V instancias realizadas del algoritmo de Dijkstra. Entonces, cuando el grafo es disperso el tiempo total del algoritmo puede ser menor que el algoritmo de Floyd-Warshall, que resuelve el mismo problema en un tiempo de O(V³).

Ejemplo

Las etapas del algoritmo de Johnson están descritas en la siguiente ilustración:

En la imagen de la izquierda tiene dos aristas negativas y no contiene ciclos negativos. En la segunda imagen se muestra el nuevo vértice q con peso 0 hacia todos los nodos. En la tercera imagen, se muestra el árbol de caminos mínimos calculado con el algoritmo de Bellman-Ford con q como vértice inicial, y los valores h(v) calculados para cada otro nodo como la longitud del camino más corto entre q y ese nodo. A modo de ilustración, en dicha imagen solo aparecen los caminos que se tomarían para determinar cada valor h(v). Nótese que todos estos valores h(v) no son positivos, porque q tiene una arista de unión con cada nodo de peso 0, y por tanto el camino más corto no puede ser mayor que ese valor. En la parte derecha se muestra el grafo modificado, hecho reemplazando el peso de cada arista w(u, v) por w(u, v) + h(u) – h(v). En este grafo modificado, todos los pesos de las aristas son positivos y el camino más corto entre dos nodos cualesquiera usa la misma secuencia de aristas que en el camino más corto entre los mismos dos nodos en el grafo original. El algoritmo concluye aplicando el algoritmo de Dijkstra para cada uno de los cuatro nodos originales en el grafo modificado (cuarta imagen).

Implementación

La estructura de datos para almacenar el grafo consiste en una representación de cada vértice como una lista de las aristas que parten del mismo. Estas aristas constan de un origen, un destino y un peso. El conjunto de vértices se representa como un array de vértices y un índice que nos indica el último vértice empleado del array.

La implementación del algoritmo devuelve una matriz de elementos precedentes y otra de distancias, mediante la primera se puede seguir el camino de menor coste desde un nodo dado a cualquier otro nodo del grafo, y si paralelamente vamos sumando las distancias de la otra matriz, obtenemos los costes totales de dichos caminos mínimos.

Pseudocódigo

   Tipos
   Arista = REGISTRO
       o : NATURAL
       d : NATURAL
       peso : INT
       sig : NATURAL
   FIN
   LAristas = PUNTERO A Arista
   TGrafo = ARRAY [1..N] DE LAristas
   THv = ARRAY [1..N] DE ENTERO
   TVector = ARRAY [1..N] DE ENTERO
   TMatriz = ARRAY [1..N] DE TVector

   //suponemos ig>1
   PROC Johnson (↓grafo: TGrafo; ↓ig: NATURAL; ↑ distancias: TMatriz ; ↑ previos: TMatriz)
   VARIABLES
       i : NATURAL
       p : LAristas
       min_caminos : THv
       aux_dist, aux_prev : TVector
   INICIO
       grafo[ig] ← nueva_arista(ig,1,0,NULO)
       inc(ig)
       p ← grafo[ig]
       PARA i ← 2 HASTA ig-2 HACER
           p^.sig ← nueva_arista(ig,i,0,NULO)
           p ← p^.sig
       FIN
       BellmanFord(grafo,ig, min_caminos)
       PARA i ← 1 HASTA ig-1 HACER
           p ← grafo[i]
           MIENTRAS (p != NULO) HACER
               p^.peso ← p^.peso + min_caminos[p^.o] - min_caminos[p^.d]
               p ← p^.sig
           FIN
       FIN
       PARA i ← 1 HASTA ig-2 HACER
           Dijkstra(grafo,i, aux_dist,aux_prev)    // devuelve los caminos mínimos desde el último nodo
                                                   // a todos los demás
           previos[i] ← aux_prev;     
           CalcularDistancias(grafo, previos, aux_dist,distancias); // este algoritmo realiza la transformación inversa a la
                                                                    // que habíamos hecho antes sobre los pesos, para obtener
                                                                    // las distancias reales
       FIN
   FIN

C++

 
#include <cstdlib>
using namespace std;

struct Arista{
    unsigned o;
    unsigned d;
    int peso;
    LAristas sig;
};
typedef LAristas Arista*;

typedef TGrafo LArista[N];

typedef TVector int[N];
typedef TMatriz TVector[N];

//suponemos ig>1
void johnson(const TGrafo &grafo, int ig, TMatriz &distancias, TMatriz &previos){
    Arista* p;
    TVector min_caminos;
    TVector aux_dist;
    TVector aux_prev;

    grafo[ig] = nueva_arista(ig,1,0,NULL);
    ig++;

    p = grafo[ig];
    for(unsigned i=2; i<=ig-2; i++){
        p->sig = nueva_arista(ig,i,0,NULL);
        p = p->sig;
    }

    BellmanFord(grafo,ig, min_caminos);

    for(unsigned i=1; i<=ig-1; i++){
        p = grafo[i];
        while(p != NULL){
            p->peso = p->peso + min_caminos[p->o] - min_caminos[p->d];
            p = p->sig;
        }
    }

    for(unsigned i=1; i<=ig-2; i++){
            Dijkstra(grafo,i-1, aux_dist,aux_prev) // devuelve los caminos mínimos desde el último nodo
                                                   // a todos los demás.
            previos[i-1] = aux_prev;
            CalcularDistancias(grafo, previos, aux_dist,distancias); // este algoritmo realiza la transformación inversa a la
                                                                     // que habíamos hecho antes sobre los pesos, para obtener
                                                                     // las distancias reales
    }
}

La implementación más adecuada del algoritmo de Dijkstra sería mediante montículos, ya que es capaz de dar los mejores resultados para que el mismo algoritmo de Johnson sea más eficiente.

Referencias

Artículos de Donald B. Johnson (Publicaciones de ACM)
Johnson, Donald B. (1977), "Efficient algorithms for shortest paths in sparse networks", Journal of the ACM
Perfil de Donald B. Johnson en el portal de ACM (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).

Datos: Q2345824
Multimedia: Johnson's algorithm / Q2345824