En informática teórica y enrutamiento de red , el algoritmo de Suurballe es un algoritmo para encontrar dos caminos separados en un gráfico dirigido no ponderado negativamente , de modo que ambos caminos conecten el mismo par de vértices y tengan una longitud total mínima. [1] El algoritmo fue concebido por John W. Suurballe y publicado en 1974. [2] La idea principal del algoritmo de Suurballe es utilizar el algoritmo de Dijkstra.para encontrar una ruta, modificar los pesos de los bordes del gráfico y luego ejecutar el algoritmo de Dijkstra por segunda vez. La salida del algoritmo se forma combinando estos dos caminos, descartando los bordes que son atravesados en direcciones opuestas por los caminos y usando los bordes restantes para formar los dos caminos para regresar como la salida. La modificación de los pesos es similar a la modificación del peso en el algoritmo de Johnson y conserva la no negatividad de los pesos al tiempo que permite que la segunda instancia del algoritmo de Dijkstra encuentre la segunda ruta correcta.
El problema de encontrar dos caminos separados de peso mínimo puede verse como un caso especial de un problema de flujo de costo mínimo , donde en este caso hay dos unidades de "flujo" y los nodos tienen una unidad de "capacidad". El algoritmo de Suurballe, también, puede verse como un caso especial de un algoritmo de flujo de costo mínimo que empuja repetidamente la máxima cantidad posible de flujo a lo largo de una ruta de aumento más corta. La primera ruta encontrada por el algoritmo de Suurballe es la ruta de aumento más corta para el flujo inicial (cero), y la segunda ruta encontrada por el algoritmo de Suurballe es la ruta de aumento más corta para el gráfico residual que queda después de empujar una unidad de flujo a lo largo de la primera ruta.
Definiciones
Sea G un gráfico dirigido ponderado con el conjunto de vértices V y el conjunto de aristas E (figura A); sea s un vértice fuente designado en G , y sea t un vértice destino designado. Deje que cada borde ( u , v ) en E , desde el vértice u al vértice v , tenga un costo no negativo w ( u , v ) .
Defina d ( s , u ) como el costo del camino más corto al vértice u desde el vértice s en el árbol del camino más corto con raíz en s (figura C).
Nota: Node y Vertex a menudo se usan indistintamente.
Algoritmo
El algoritmo de Suurballe realiza los siguientes pasos:
- Encuentre el árbol de ruta más corto T enraizado en el nodo s ejecutando el algoritmo de Dijkstra (figura C). Éste árbol tiene para cada vértice u , un camino más corto desde s a u . Deje P 1 sea el camino más corto costo de s a t (figura B). Los bordes en T se denominan bordes de árbol y los bordes restantes (los bordes que faltan en la figura C) se denominan bordes que no son de árbol .
- Modifique el costo de cada borde en la gráfica reemplazando el costo w ( u , v ) de cada borde ( u , v ) por w ′ ( u , v ) = w ( u , v ) - d ( s , v ) + d ( s , u ) . De acuerdo con la función de costo modificado resultante, todos los bordes de los árboles tienen un costo de 0 y los bordes que no son de árboles tienen un costo no negativo. Por ejemplo:
Si u = B, v = E , entonces w ′ ( u , v ) = w (B, E) - d (A, E) + d (A, B) = 2 - 3 + 1 = 0
Si u = E, v = B , entonces w ′ ( u , v ) = w (E, B) - d (A, B) + d (A, E) = 2 - 1 + 3 = 4 - Cree un gráfico residual G t formado a partir de G eliminando los bordes de G en la trayectoria P 1 que se dirigen hacia sy luego invierta la dirección de los bordes de longitud cero a lo largo de la trayectoria P 1 (figura D).
- Encuentre el camino más corto P 2 en el gráfico residual G t ejecutando el algoritmo de Dijkstra (figura E).
- Deseche los bordes invertidos de P 2 de ambos caminos. Las aristas restantes de P 1 y P 2 forman un subgrafo con dos aristas salientes en s , dos aristas entrantes en t , y una arista entrante y una saliente en cada vértice restante. Por lo tanto, este subgrafo consta de dos caminos de borde disjunta de s a t y posiblemente algunos ciclos adicionales (de longitud cero). Devuelve las dos rutas disjuntas del subgrafo.
Ejemplo
El siguiente ejemplo muestra cómo el algoritmo de Suurballe encuentra el par más corto de caminos disjuntos de A a F .
La figura A ilustra un gráfico ponderado G .
La Figura B calcula la ruta más corta P 1 de A a F ( A - B - D - F ).
La Figura C ilustra el árbol de camino más corto T con raíz en A , y las distancias calculadas desde A hasta cada vértice ( u ).
La Figura D muestra el gráfico residual G t con el costo actualizado de cada borde y los bordes de la ruta P 1 invertidos.
La Figura E calcula la trayectoria P 2 en el gráfico residual G t ( A - C - D - B - E - F ).
La Figura F ilustra tanto la ruta P 1 como la ruta P 2 .
La Figura G encuentra el par más corto de caminos disjuntos combinando los bordes de los caminos P 1 y P 2 y luego descartando los bordes invertidos comunes entre ambos caminos ( B - D ). Como resultado, obtenemos el par más corto de caminos disjuntos ( A - B - E - F ) y ( A - C - D - F ).
Exactitud
El peso de cualquier camino de s a t en el sistema modificado de los pesos es igual al peso en el gráfico original, menos d ( s , t ) . Por lo tanto, los dos caminos disjuntos más cortos bajo los pesos modificados son los mismos caminos que los dos caminos más cortos en el gráfico original, aunque tienen pesos diferentes.
El algoritmo de Suurballe puede ser visto como un caso especial del método de trayectorias más cortas sucesivas para encontrar un flujo de costo mínimo con la cantidad total de flujo de dos de s a t . La modificación de los pesos no afecta la secuencia de rutas encontradas por este método, solo sus pesos. Por lo tanto, la corrección del algoritmo se deriva de la corrección del método de las rutas sucesivas más cortas.
Análisis y tiempo de ejecución
Este algoritmo requiere dos iteraciones del algoritmo de Dijkstra. Usando montones de Fibonacci , ambas iteraciones se pueden realizar a tiempo dónde y son el número de vértices y aristas respectivamente. Por lo tanto, el mismo límite de tiempo se aplica al algoritmo de Suurballe.
Variaciones
La versión del algoritmo de Suurballe como se describe arriba encuentra caminos que tienen bordes disjuntos, pero que pueden compartir vértices. Es posible usar el mismo algoritmo para encontrar caminos de vértice-disjuntos, reemplazando cada vértice por un par de vértices adyacentes, uno con todas las adyacencias entrantes u-in del vértice original y otro con todas las adyacencias salientes u -fuera . Dos rutas de bordes disjuntos en este gráfico modificado corresponden necesariamente a dos rutas de vértices disjuntos en el gráfico original y viceversa, por lo que la aplicación del algoritmo de Suurballe al gráfico modificado da como resultado la construcción de dos rutas de vértices disjuntos en el gráfico original. El algoritmo original de 1974 de Suurballe era para la versión de vértice disjunto del problema, y fue ampliado en 1984 por Suurballe y Tarjan a la versión de borde disjunto. [3]
Al usar una versión modificada del algoritmo de Dijkstra que calcula simultáneamente las distancias a cada vértice t en los gráficos G t , también es posible encontrar las longitudes totales de los pares de caminos más cortos desde un vértice fuente dado s hasta cualquier otro vértice en el gráfico, en una cantidad de tiempo que es proporcional a una sola instancia del algoritmo de Dijkstra.
Nota: El par de vértices adyacentes que resultan de la división están conectados por un borde unidireccional de costo cero desde el vértice entrante al saliente. El vértice de origen se convierte en s-out y el vértice de destino se convierte en t-in .
Ver también
Referencias
- ^ Bhandari, Ramesh (1999), "Algoritmos de pares disjuntos de Suurballe", Redes de supervivencia: algoritmos para enrutamiento diverso , Springer-Verlag, págs. 86-91, ISBN 978-0-7923-8381-9.
- ^ Suurballe, JW (1974), "Rutas disjuntas en una red", Networks , 4 (2): 125–145, doi : 10.1002 / net.3230040204.
- ^ Suurballe, JW; Tarjan, RE (1984), "Un método rápido para encontrar los pares más cortos de caminos disjuntos" (PDF) , Networks , 14 (2): 325–336, doi : 10.1002 / net.3230140209.