Algoritmo de Johnson

Método de búsqueda de ruta basado en computadora

El algoritmo de Johnson es una forma de encontrar los caminos más cortos entre todos los pares de vértices en un grafo dirigido ponderado por aristas . Permite que algunos de los pesos de las aristas sean números negativos , pero no pueden existir ciclos de peso negativo . Funciona utilizando el algoritmo 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]} Lleva el 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 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 arista no negativos. ^[4]

Descripción del algoritmo

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

1. Primero, se agrega un nuevo nodo q al gráfico, conectado mediante aristas de peso cero a cada uno de los otros nodos.
2. En segundo lugar, se utiliza el algoritmo Bellman-Ford , comenzando desde el 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, los bordes del gráfico original se vuelven a ponderar utilizando los valores calculados por el algoritmo Bellman-Ford: a un borde de u a v , que tiene una longitud ⁠ ⁠ ${\displaystyle w(u,v)}$ , se le asigna la nueva longitud w ( u , v ) + h ( u ) − h ( v ) .
4. Finalmente, se elimina q y se utiliza el algoritmo de Dijkstra para encontrar las rutas más cortas desde cada nodo s hasta cada uno de los demás vértices del gráfico reponderado. Luego, se calcula la distancia en el gráfico original 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 representan 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 del centro muestra el nuevo vértice q , un árbol de ruta más corta calculado por el algoritmo Bellman-Ford con q como vértice inicial, y los valores h ( v ) calculados en cada nodo como la longitud de la ruta más corta desde q hasta ese nodo. Nótese que estos valores no son todos positivos, porque q tiene una arista de longitud cero hacia cada vértice y la ruta más corta no puede ser más larga que esa arista. A la derecha se muestra el gráfico reponderado, formado al reemplazar cada peso de arista ⁠ ⁠ por ${\displaystyle w(u,v)}$ w ( u , v ) + h ( u ) − h ( v ) . En este gráfico reponderado, todos los pesos de las aristas no son negativos, pero la ruta más corta entre dos nodos cualesquiera usa 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.

Exactitud

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 camino ${\displaystyle s-t}$ . Su peso W en el grafo 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 se cancela en la expresión entre corchetes anterior; por lo tanto, nos queda la siguiente expresión para W : ${\displaystyle +h(p_{i})}$ ${\displaystyle -h(p_{i})}$

$${\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 la reponderación añade la misma cantidad al peso de cada ruta , ${\displaystyle s-t}$ una ruta es una ruta más corta en la ponderación original si y solo si es una ruta más corta después de la reponderación. El peso de las aristas que pertenecen a una ruta más corta desde q a cualquier nodo es cero y, por lo tanto, las longitudes de las rutas más cortas desde q a cada nodo se vuelven cero en el grafo reponderado; sin embargo, siguen siendo rutas más cortas. Por lo tanto, no puede haber aristas negativas: si la arista uv tuviera un peso negativo después de la reponderación, entonces la ruta de longitud cero desde q a u junto con esta arista formaría una ruta de longitud negativa desde q a v , contradiciendo el hecho de que todos los vértices tienen distancia cero desde q . La no existencia de aristas negativas asegura la optimalidad de las rutas encontradas 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]

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 tiempo para la etapa Bellman–Ford del algoritmo y para cada una de las instancias del algoritmo de Dijkstra. Por lo tanto, cuando el grafo es escaso , el tiempo total puede ser más rápido que el algoritmo Floyd–Warshall , que resuelve el mismo problema en tiempo . ^[1] ${\displaystyle O(|V|^{2}\log |V|+|V||E|)}$ ${\displaystyle O(|V||E|)}$ ${\displaystyle O(|V|\log |V|+|E|)}$ ${\displaystyle |V|}$ ${\displaystyle O(|V|^{3})}$

Referencias

1. 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.
2. Black, Paul E. (2004), "Algoritmo de Johnson", Diccionario de algoritmos y estructuras de datos, Instituto Nacional de Estándares y Tecnología.
3. 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.
4. Suurballe, JW (1974), "Caminos disjuntos en una red", Redes , 14 (2): 125–145, doi :10.1002/net.3230040204.

Enlaces externos

• Impulso: todos los pares de caminos más cortos