Algoritmo de Johnson

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.

Contenido

Descripción del algoritmo

El algoritmo de Johnson consiste en los siguientes pasos:

  1. 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.
  2. 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.
  3. 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)
  4. 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(V2log 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(V3).

Ejemplo

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

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


Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • Check Wikipedia — Wikiproyecto:Check Wikipedia Saltar a navegación, búsqueda Esta página contiene de forma consciente fallos ortográficos. Los bots no deben intentar corregirlos. Atajo PR:CWPR:CW …   Wikipedia Español

  • Problema de los caminos más cortos — Saltar a navegación, búsqueda Ejemplo de Grafo Ponderado En la Teoría de grafos, el problema de los caminos más cortos es el problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las… …   Wikipedia Español

  • Centralidad — Saltar a navegación, búsqueda Un ejemplo de centralidad se muestra en el grafo de la ilustración, la intermediación se grada mediante colores que van desde el rojo con un bajo valor de intermediación hasta el azul con un valor máximo. Dentro de… …   Wikipedia Español

  • NP-completo — En teoría de la complejidad computacional, la clase de complejidad NP completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP completo. Se puede decir que los… …   Wikipedia Español

  • Segmentación (procesamiento de imágenes) — La segmentación en el campo de la visión artificial es el proceso de dividir una imagen digital en varias partes (grupos de píxeles) u objetos. El objetivo de la segmentación es simplificar y/o cambiar la representación de una imagen en otra más… …   Wikipedia Español

  • Problema de la suma de subconjuntos — Saltar a navegación, búsqueda El problema de la suma de subconjuntos es un problema importante en la teoría de la complejidad y en la criptografía. El problema es este: dado un conjunto de enteros, ¿existe algún subconjunto cuya suma sea… …   Wikipedia Español

  • Tiempo polinomial incremental — En complejidad computacional, el tiempo polinomial incremental (en inglés incremental polynomial delay) se refiere a cuando el tiempo de ejecución de un algoritmo de enumeración de un conjunto es polinomial en términos de la entrada y de los… …   Wikipedia Español

  • Conexionismo — El conexionismo es un conjunto de enfoques en los ámbitos de la inteligencia artificial, psicología cognitiva, ciencia cognitiva, neurociencia y filosofía de la mente, que presenta los fenómenos de la mente y del comportamiento como procesos que… …   Wikipedia Español

  • Diff — Saltar a navegación, búsqueda En informática, diff es una utilidad para la comparación de archivos que genera las diferencias entre dos archivos o los cambios realizados en un archivo determinado comparándolo con una versión anterior del mismo… …   Wikipedia Español

  • Esteganografía — Saltar a navegación, búsqueda Este artículo trata sobre Transporte de Mensajes Ocultos. Aún requiere correcciones. Para Estenografía, véase Taquigrafía. La esteganografía es la disciplina en la que se estudian y aplican técnicas que permiten el… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”