algoritmo de johnson

El algoritmo de Johnson es una forma de encontrar los caminos más cortos entre todos los pares de vértices en un gráfico dirigido con aristas ponderadas . Permite que algunos de los pesos de los bordes sean números negativos , pero no pueden existir ciclos de pesos negativos . Funciona utilizando el algoritmo de Bellman-Ford para calcular una transformación del gráfico de entrada que elimina todos los pesos negativos, lo que permite utilizar el algoritmo de Dijkstra en el gráfico transformado. ^[1]^[2] Lleva el nombre de Donald B. Johnson , quien publicó la técnica por primera vez en 1977. ^[3]

También se utiliza una técnica de reponderación similar en el algoritmo de Suurballe para encontrar dos caminos disjuntos de longitud total mínima entre los mismos dos vértices en un gráfico con pesos de borde no negativos. ^[4]

Descripción del algoritmo

El algoritmo de Johnson consta de los siguientes pasos: ^[1]^[2]

Primero, se agrega un nuevo nodo $q$ al gráfico, conectado mediante bordes de peso cero a cada uno de los otros nodos.
En segundo lugar, se utiliza el algoritmo de Bellman-Ford , a partir del nuevo vértice $q$ , para encontrar para cada vértice $v$ el peso mínimo $h (v)$ de un camino de $q$ a $v$ . Si este paso detecta un ciclo negativo, el algoritmo finaliza.
A continuación, los bordes del gráfico original se vuelven a ponderar utilizando los valores calculados por el algoritmo de Bellman-Ford: un borde de $u$ a $v$ , que tiene longitud , recibe la nueva longitud $w$ $($ $u$ $,$ $v$ $) +$ $h$ $($ $u$ $) -$ $h$ $($ $v$ $)$ . $w(u,v)$
Finalmente, se elimina $q$ y se utiliza el algoritmo de Dijkstra para encontrar los caminos más cortos desde cada nodo $s$ hasta todos los demás vértices en el gráfico reponderado. Luego, la distancia en el gráfico original se calcula para cada distancia $D$ ( $u$ , $v$ ), sumando $h (v) - h (u)$ a la distancia devuelta por el algoritmo de Dijkstra.

Ejemplo

Las primeras tres etapas del algoritmo de Johnson se muestran en la siguiente ilustración.

El gráfico de la izquierda de la ilustración tiene dos aristas negativas, pero ningún ciclo negativo. El gráfico central muestra el nuevo vértice $q$ , un árbol de camino más corto calculado por el algoritmo de Bellman-Ford con $q$ como vértice inicial, y los valores $h (v)$ calculados en cada otro nodo como la longitud del camino más corto desde $q$ hasta ese nodo. Tenga en cuenta que todos estos valores no son positivos, porque $q$ tiene un borde de longitud cero en cada vértice y el camino más corto no puede ser más largo que ese borde. A la derecha se muestra el gráfico reponderado, formado reemplazando cada peso de borde por $w$ $($ $u$ $,$ $v$ $) +$ $h$ $($ $u$ $) -$ $h$ $($ $v$ $)$ . En este gráfico reponderado, todas las ponderaciones de los bordes no son negativas, pero la ruta más corta entre dos nodos cualesquiera utiliza la misma secuencia de aristas que la ruta más corta entre los mismos dos nodos en el gráfico original. El algoritmo concluye aplicando el algoritmo de Dijkstra a cada uno de los cuatro nodos iniciales en el gráfico reponderado. $w(u,v)$

Exactitud

En el gráfico reponderado, a todos los caminos entre un par $s$ y $t$ de nodos se les agrega la misma cantidad $h (s) - h (t) .$ La afirmación anterior se puede demostrar de la siguiente manera: Sea $p$ un camino. Su peso W en el gráfico reponderado viene dado por la siguiente expresión: $st$

{\bigl (}w(s,p_{1})+h(s)-h(p_{1}){\bigr )}+{\bigl (}w(p_{1},p_{ 2})+h(p_{1})-h(p_{2}){\bigr )}+...+{\bigl (}w(p_{n},t)+h(p_{n} )-h(t){\bigr )}.

Cada se cancela por en la expresión entre corchetes anterior; por lo tanto, nos queda la siguiente expresión para W : $+h(p_{i})$ $-h(p_{i})$

{\bigl (}w(s,p_{1})+w(p_{1},p_{2})+...+w(p_{n},t){\bigr )}+ h(s)-h(t)

La expresión entre corchetes es el peso de p en la ponderación original.

Dado que la reponderación agrega la misma cantidad al peso de cada ruta, una ruta es la ruta más corta en la ponderación original si y solo si es la ruta más corta después de la reponderación. El peso de los bordes que pertenecen a un camino más corto desde q a cualquier nodo es cero y, por lo tanto, las longitudes de los caminos más cortos desde q a cada nodo se vuelven cero en el gráfico reponderado; sin embargo, siguen siendo caminos más cortos. Por lo tanto, no puede haber aristas negativas: si la arista uv tuviera un peso negativo después de la reponderación, entonces el camino de longitud cero de q a u junto con este borde formaría un camino de longitud negativa de q a v , lo que contradice el hecho de que todos los vértices tienen distancia cero de q . La no existencia de aristas negativas asegura la optimización de los caminos encontrados por el algoritmo de Dijkstra. Las distancias en el gráfico original se pueden calcular a partir de las distancias calculadas por el algoritmo de Dijkstra en el gráfico reponderado invirtiendo la transformación de reponderación. ^[1] $st$

Análisis

La complejidad temporal de este algoritmo, que utiliza montones de Fibonacci en la implementación del algoritmo de Dijkstra, es : el algoritmo utiliza el tiempo para la etapa Bellman-Ford del algoritmo y para cada una de las instancias del algoritmo de Dijkstra. Así, cuando el gráfico es disperso , el tiempo total puede ser más rápido que el algoritmo de Floyd-Warshall , que resuelve el mismo problema en el tiempo . ^[1] $O(|V|^{2}\log |V|+|V||E|)$ $O(|V||E|)$ $O(|V|\log |V|+|E|)$ $|V|$ $O(|V|^{3})$

Referencias

^ abcd Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001), Introducción a los algoritmos , MIT Press y McGraw-Hill, ISBN 978-0-262-03293-3. Sección 25.3, "Algoritmo de Johnson para gráficos dispersos", págs. 636–640.
^ ab Black, Paul E. (2004), "Algoritmo de Johnson", Diccionario de algoritmos y estructuras de datos, Instituto Nacional de Estándares y Tecnología.
^ Johnson, Donald B. (1977), "Algoritmos eficientes para caminos más cortos en redes dispersas", Journal of the ACM , 24 (1): 1–13, doi : 10.1145/321992.321993 , S2CID 207678246.
^ Suurballe, JW (1974), "Rutas disjuntas en una red", Redes , 14 (2): 125–145, doi :10.1002/net.3230040204.

enlaces externos

Impulso: Todos los pares de caminos más cortos