Algoritmo de Eppstein y algoritmo de Yen para k caminos más cortos

Question

Estoy tratando de entender exactamente cómo funcionan estos algoritmos, pero no he podido encontrar una explicación simple. Le agradecería enormemente si alguien pudiera proporcionarme o señalarme una descripción de estos algoritmos que sea más fácil de comprender que la descripción en los documentos originales. Gracias.

Answer 1

Antes que nada, permítame proporcionarle los enlaces a los documentos de los que estaba hablando. papel

de Eppstein: D. Eppstein, “Finding the k shortest paths,” SIAM J. Comput., vol. 28, no. 2, pp.652–673, Feb. 1999

papel de Yen: J. Y. Yen, “Finding the K Shortest Loopless Paths in a Network,” Management Science, vol. 17, no. 11, pp. 712–716, 1971.

Aquí está mi explicación del algoritmo de Yen:

algoritmo de Yen utiliza dos listas, es decir, la lista A (caminos más cortos permanentes del origen al destino - ordenado cronológicamente) y la lista B (rutas más cortas tentativas/candidatas). Al principio, debe encontrar la primera ruta más corta desde la fuente hasta el destino utilizando cualquier algoritmo de ruta más corta bien adaptado (por ejemplo, Dijkstra). Entonces Yen explota la idea de que las rutas k-th más cortas pueden compartir bordes y subrutas (ruta desde la fuente a cualquier nodo intermediario dentro de la ruta) desde (k-1) -la ruta más corta. Luego debe tomar (k-1) la ruta más corta y hacer que cada nodo en la ruta sea inalcanzable, es decir, rozar un borde particular que va al nodo dentro de la ruta. Una vez que el nodo es inalcanzable, encuentre la ruta más corta desde el nodo precedente al destino. Luego tiene una nueva ruta que se crea al agregar la subruta común (desde el origen hasta el nodo anterior del nodo inalcanzable) y agrega la nueva ruta más corta desde el nodo anterior al destino. Esta ruta luego se agrega a la lista B, siempre que no haya aparecido antes en la lista A o en la lista B. Después de repetir esto para todos los nodos en la ruta, debe encontrar la ruta más corta en la lista B y moverla a la lista A. Simplemente debe repetir este proceso por la cantidad de K que tenga.

Este algoritmo tiene una complejidad computacional de O (kn^3). Por favor, lea el documento para más detalles.

El algoritmo es el siguiente:

G = Adjacent Matrix of the Network 
Initialize: 
A_1 = shortest-path from source to destination 
Glocal ← Local copy of G 
for k = 2 → K do 
for i = 1 → [len(A_(k−1)) − 1] do 
    Current Node ← A_(k−1) [i] 
    Ri ← Sub-path (root) from source till current node in A_(k−1) 
    for j = 1 → k − 1 do 
    Rj ← Sub-path (root) from source till current node in A_j 
    if Ri == Rj then 
    Next Node ← Aj [i+1] 
    Glocal(Current Node, Next Node) ← infinity 
    Current Node ← unreachable 
    end if 
    end for 
    Si ← Shortest-path from current node till destination 
    Bi ← Ri + Si 
end for 
A_k ← Shortest-path amongst all paths in B 
Restore original graph: Glocal ← Local copy of G 
end for 

Por desgracia, no he utilizado uno de Eppstein como el algoritmo de Yen era óptima para mi problema.

Espero que esto ayude. Aclamaciones.

=====

Editar:

Por favor, echar un vistazo a la wikipedia entry también. Tiene un buen ejemplo.

=====

Editar:

he encontrado algunas implementaciones en C. Los enlaces son como sigue:

Eppstein implementation y Loading Graph for Eppstein.

Si usted está interesado, hay un lazy version de Eppstein.El enlace es el siguiente:

Lazy Eppstein by Jimenez and Marzal

=====

Editar:

Sólo otro link. Éste contiene varias implementaciones (C/C++).

=====

Editar:

he encontrado un good explanation del algoritmo de Eppstein.