El algoritmo de Johnson

El algoritmo de Johnson es un método para encontrar los caminos más cortos entre todos los pares de vértices en un grafo dirigido con pesos en las aristas . Permite que algunos pesos de las aristas sean negativos , pero no puede haber ciclos con pesos negativos . Funciona utilizando el algoritmo de Bellman-Ford para calcular una transformación del grafo de entrada que elimina todos los pesos negativos, lo que permite utilizar el algoritmo de Dijkstra en el grafo transformado. ^{[ 1 ] [ 2 ]} Recibe su nombre de Donald B. Johnson , quien publicó la técnica por primera vez en 1977. ^{[ 3 ]}

Una técnica de reponderación similar también se utiliza en una versión del algoritmo de caminos más cortos sucesivos para el problema del flujo de costo mínimo debido a Edmonds y Karp, ^{[ 4 ]} así como en el algoritmo de Suurballe para encontrar dos caminos disjuntos de longitud total mínima entre los mismos dos vértices en un grafo con pesos de aristas no negativos. ^{[ 5 ]}

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

1. En primer lugar, se añade un nuevo nodo q al grafo, conectado mediante aristas de peso cero a cada uno de los demás nodos.
2. En segundo lugar, se utiliza el algoritmo de Bellman-Ford , partiendo del nuevo vértice q , para encontrar, para cada vértice v, el peso mínimo h ( v ) de un camino desde q hasta v . Si este paso detecta un ciclo negativo, el algoritmo finaliza.
3. A continuación, las aristas del grafo original se reponderan utilizando los valores calculados por el algoritmo de Bellman-Ford: una arista de u a v , con longitud ⁠${\displaystyle w(u,v)}$⁠ , se le da la nueva longitud w ( u , v ) + h ( u ) − h ( v ) .
4. Finalmente, se elimina q y se utiliza el algoritmo de Dijkstra para encontrar los caminos más cortos desde cada nodo s a todos los demás vértices del grafo ponderado nuevamente. Luego, se calcula la distancia en el grafo original para cada distancia D ( u , v ), sumando h ( v ) − h ( u ) a la distancia devuelta por el algoritmo de Dijkstra.

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

El grafo de la izquierda de la ilustración tiene dos aristas negativas, pero ningún ciclo negativo. El grafo central muestra el nuevo vértice q , un árbol de caminos más cortos calculado mediante 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. Nótese que todos estos valores son no positivos, porque q tiene una arista de longitud cero a cada vértice y el camino más corto no puede ser más largo que esa arista. A la derecha se muestra el grafo reponderado, formado al reemplazar el peso de cada arista .${\displaystyle w(u,v)}$⁠ por w ( u , v ) + h ( u ) − h ( v ) . En este grafo ponderado, todos los pesos de las aristas son no negativos, pero el camino más corto entre dos nodos cualesquiera utiliza la misma secuencia de aristas que el camino más corto entre los mismos dos nodos en el grafo original. El algoritmo concluye aplicando el algoritmo de Dijkstra a cada uno de los cuatro nodos iniciales del grafo ponderado.

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

$${\displaystyle \left(w(s,p_{1})+h(s)-h(p_{1})\right)+\left(w(p_{1},p_{2})+h(p_{1})-h(p_{2})\right)+...+\left(w(p_{n},t)+h(p_{n})-h(t)\right).}$$

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

$${\displaystyle \left(w(s,p_{1})+w(p_{1},p_{2})+\cdots +w(p_{n},t)\right)+h(s)-h(t)}$$

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

Dado que el reponderado añade la misma cantidad al peso de cada uno${\displaystyle st}$Un camino es el camino más corto en la ponderación original si y solo si sigue siendo el camino más corto después de la reponderación. El peso de las aristas 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 grafo 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 desde q a u junto con esta arista formaría un camino de longitud negativa desde q a v , lo que contradice el hecho de que todos los vértices tienen distancia cero desde q . La no existencia de aristas negativas garantiza la optimalidad de los caminos encontrados por el algoritmo de Dijkstra. Las distancias en el grafo original se pueden calcular a partir de las distancias calculadas por el algoritmo de Dijkstra en el grafo reponderado invirtiendo la transformación de reponderación. ^{[ 1 ]}

La complejidad temporal de este algoritmo, utilizando montículos de Fibonacci en la implementación del algoritmo de Dijkstra, es${\displaystyle O(|V|^{2}\log |V|+|V||E|)}$: el algoritmo utiliza${\displaystyle O(|V||E|)}$tiempo para la etapa Bellman-Ford del algoritmo, y${\displaystyle O(|V|\log |V|+|E|)}$para cada uno de los${\displaystyle |V|}$instanciaciones del algoritmo de Dijkstra. Por lo tanto, cuando el grafo es disperso , el tiempo total puede ser más rápido que el algoritmo de Floyd-Warshall , que resuelve el mismo problema en tiempo${\displaystyle O(|V|^{3})}$. ^{[ 1 ]}

• Boost: Rutas más cortas para todos los pares