El algoritmo de Johnson es una manera de encontrar las rutas más cortas entre todos los pares de vértices en un borde ponderados , grafo dirigido . Permite que algunos de los pesos de los bordes sean números negativos , pero es posible que no existan ciclos de peso negativo . Funciona mediante 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ó por primera vez la técnica en 1977. [3]
Clase | Problema de la ruta más corta de todos los pares (para gráficos ponderados) |
---|---|
Estructura de datos | Grafico |
Rendimiento en el peor de los casos |
También se utiliza una técnica de reponderación similar en el algoritmo de Suurballe para encontrar dos caminos separados 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 por bordes de peso cero a cada uno de los otros nodos.
- En segundo lugar, se utiliza el algoritmo de Bellman-Ford , comenzando desde el nuevo vértice q , para encontrar para cada vértice v el peso mínimo h ( v ) de una trayectoria 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 una longitud, se le da la nueva longitud w ( u , v ) + h ( u ) - h ( v ) .
- Finalmente, se elimina q y se usa el algoritmo de Dijkstra para encontrar las rutas más cortas desde cada nodo s hasta cada otro vértice en el gráfico reponderado. La distancia en el gráfico original se calcula luego para cada distancia D ( u , v ), agregando 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 bordes negativos, pero ningún ciclo negativo. El gráfico central muestra el nuevo vértice q , un árbol de ruta 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 de la ruta más corta de q a 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 al reemplazar cada peso de bordepor w ( u , v ) + h ( u ) - h ( v ) . En este gráfico reponderado, todos los pesos de los bordes no son negativos, pero la ruta más corta entre dos nodos usa la misma secuencia de bordes 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 gráfico reponderadas, todas las rutas entre un par s y t de nodos tienen la misma cantidad h ( s ) - h ( t ) añadido a ellos. El enunciado anterior se puede probar de la siguiente manera: Sea p uncamino. Su peso W en el gráfico reponderado viene dado por la siguiente expresión:
Cada es cancelado por en la expresión anterior entre corchetes; por lo tanto, nos queda la siguiente expresión para W :
La expresión entre corchetes es la ponderación de p en la ponderación original.
Dado que la reponderación agrega la misma cantidad al peso de cada ruta, 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 volver a ponderar. El peso de los bordes 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 gráfico reponderado; sin embargo, siguen siendo los caminos más cortos. Por lo tanto, no puede haber bordes negativos: si borde uv tenía un peso negativo después de la ponderación, la ruta de longitud cero de q a u junto con este borde formaría un camino negativo de longitud de q para v , contradiciendo el hecho de que todos los vértices tienen una distancia cero de q . La inexistencia de bordes negativos 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]
Análisis
La complejidad temporal de este algoritmo, utilizando 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 uno de los instanciaciones del algoritmo de Dijkstra. Por lo tanto, cuando la gráfica es escasa , el tiempo total puede ser más rápido que el algoritmo de Floyd-Warshall , que resuelve el mismo problema en el tiempo.. [1]
Referencias
- ↑ a b c d 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.
- ^ a b 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 rutas más cortas en redes dispersas", Journal of the ACM , 24 (1): 1–13, doi : 10.1145 / 321992.321993.
- ^ Suurballe, JW (1974), "Rutas disjoint en una red", Networks , 14 (2): 125–145, doi : 10.1002 / net.3230040204.
enlaces externos
- Impulso: todos los pares de caminos más cortos