El algoritmo de Suurballe

En informática teórica y enrutamiento de redes , el algoritmo de Suurballe es un algoritmo para encontrar dos caminos disjuntos en un grafo dirigido con pesos no negativos , 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 usar el algoritmo de Dijkstra para encontrar un camino, modificar los pesos de las aristas del grafo y luego ejecutar el algoritmo de Dijkstra una segunda vez. La salida del algoritmo se forma combinando estos dos caminos, descartando las aristas que son recorridas en direcciones opuestas por los caminos y usando las aristas restantes para formar los dos caminos que se devuelven como salida. La modificación de los pesos es similar a la modificación de pesos en el algoritmo de Johnson y preserva la no negatividad de los pesos al tiempo que permite que la segunda instancia del algoritmo de Dijkstra encuentre el segundo camino correcto.

El problema de encontrar dos caminos disjuntos de peso mínimo puede considerarse un caso particular de un problema de flujo de costo mínimo , donde en este caso hay dos unidades de "flujo" y los nodos tienen una "capacidad" unitaria. El algoritmo de Suurballe también puede considerarse un caso particular de un algoritmo de flujo de costo mínimo que empuja repetidamente la cantidad máxima posible de flujo a lo largo de un camino de aumento más corto. El primer camino encontrado por el algoritmo de Suurballe es el camino de aumento más corto para el flujo inicial (cero), y el segundo camino encontrado por el algoritmo de Suurballe es el camino de aumento más corto para el grafo residual que queda después de empujar una unidad de flujo a lo largo del primer camino.

Sea G un grafo dirigido ponderado con conjunto de vértices V y conjunto de aristas E (figura A); sea s un vértice de origen designado en G , y sea t un vértice de destino designado. Sea cada arista ( u , v ) en E , desde el vértice u hasta el vértice v , con un costo no negativo w ( u , v ) .

Definimos d( s , u ) como el costo del camino más corto al vértice u desde el vértice s en el árbol de caminos más cortos con raíz en s (figura C).

Nota: Los términos nodo y vértice se suelen usar indistintamente.

El algoritmo de Suurballe realiza los siguientes pasos:

1. Encuentra el árbol de caminos más cortos T con raíz en el nodo s ejecutando el algoritmo de Dijkstra (figura C). Este árbol contiene para cada vértice u , un camino más corto de s a u . Sea P ₁ el camino de menor costo de s a t (figura B). Las aristas en T se llaman aristas del árbol y las aristas restantes (las que faltan en la figura C) se llaman aristas que no pertenecen al árbol .
2. Modifique el costo de cada arista en el grafo reemplazando el costo w ( u , v ) de cada arista ( u , v ) por w' ( u , v ) = w ( u , v ) − d( s , v ) + d( s , u ) . Según la función de costo modificada resultante, todas las aristas del árbol tienen un costo de 0, y las aristas que no pertenecen al árbol 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.
3. Cree un grafo residual G _t formado a partir de G eliminando las aristas de G en el camino P ₁ que están dirigidas hacia s y luego invierta la dirección de las aristas de longitud cero a lo largo del camino P ₁ (figura D).
4. Encuentra el camino más corto P ₂ en el grafo residual G _t ejecutando el algoritmo de Dijkstra (figura E).
5. Descarta las aristas invertidas de P2 de ambos caminos. Las aristas restantes de _P1 y P2 _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 disjuntos de s a t y posiblemente algunos ciclos adicionales (de longitud cero). Devuelve los dos caminos disjuntos del subgrafo.

El siguiente ejemplo muestra cómo el algoritmo de Suurballe encuentra el par más corto de caminos disjuntos desde A hasta F.

La figura A ilustra un gráfico ponderado G.

La figura B calcula el camino más corto P ₁ desde A hasta F ( A – B – D – F ).

La figura C ilustra el árbol de ruta más corta T con raíz en A , y las distancias calculadas desde A a cada vértice ( u ).

La figura D muestra el grafo residual G _t con el costo actualizado de cada arista y las aristas del camino P ₁ invertidas.

La figura E calcula la ruta P ₂ en el gráfico residual G _t ( A – C – D – B – E – F ).

La figura F ilustra tanto la ruta P ₁ como la ruta P ₂ .

La figura G encuentra el par más corto de caminos disjuntos combinando las aristas de los caminos P ₁ y P ₂ y luego descartando las aristas comunes invertidas entre ambos caminos ( B – D ). Como resultado, obtenemos los dos pares más cortos de caminos disjuntos ( A – B – E – F ) y ( A – C – D – F ).

El peso de cualquier camino de s a t en el sistema de pesos modificado es igual al peso en el grafo original, menos d( s , t ) . Por lo tanto, los dos caminos disjuntos más cortos bajo los pesos modificados son los mismos que los dos caminos más cortos en el grafo original, aunque tengan pesos diferentes.

El algoritmo de Suurballe puede considerarse un caso particular del método de caminos más cortos sucesivos para encontrar un flujo de costo mínimo con un flujo total de dos desde s hasta t . La modificación de los pesos no afecta la secuencia de caminos encontrados 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 caminos más cortos sucesivos.

Este algoritmo requiere dos iteraciones del algoritmo de Dijkstra. Usando montículos de Fibonacci , ambas iteraciones se pueden realizar en tiempo${\displaystyle O(|E|+|V|\log |V|)}$dónde${\displaystyle |V|}$y${\displaystyle |E|}$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.

La versión del algoritmo de Suurballe descrita anteriormente encuentra caminos con aristas disjuntas, pero que pueden compartir vértices. Es posible usar el mismo algoritmo para encontrar caminos con vértices 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-out . Dos caminos con aristas disjuntas en este grafo modificado corresponden necesariamente a dos caminos con vértices disjuntos en el grafo original, y viceversa; por lo tanto, al aplicar el algoritmo de Suurballe al grafo modificado se construyen dos caminos con vértices disjuntos en el grafo original. El algoritmo original de Suurballe de 1974 era para la versión con vértices disjuntos del problema, y ​​fue extendido en 1984 por Suurballe y Tarjan a la versión con aristas disjuntas. ^{[ 3 ]}

Al utilizar una versión modificada del algoritmo de Dijkstra que calcula simultáneamente las distancias a cada vértice t en los grafos G _t , también es posible encontrar las longitudes totales de los pares de caminos más cortos desde un vértice de origen s dado a todos los demás vértices del grafo, en un tiempo proporcional al de una sola instancia del algoritmo de Dijkstra.

Nota: El par de vértices adyacentes resultantes de la división están conectados por una arista unidireccional de coste cero desde el vértice de entrada al de salida. El vértice de origen se convierte en s-out y el vértice de destino en t-in .