Encontrar la ruta k-más corta entre dos nodos

9

Dado un dígrafo ponderado y una función de peso, , normalmente se puede usar el algoritmo de Dijkstra para obtener el camino más corto. Lo que me interesa es cómo obtener la ruta -shortest, la -shortest, y así sucesivamente.d ( u , v ) 2 n d 3 r dsol=V,mire(tu,v)2nortere3rre

Preguntas:

¿Existe un algoritmo eficiente para obtener la i-ésima ruta más corta entre dos nodos en un gráfico ponderado?

¿Existe un algoritmo eficiente para obtener las k rutas más cortas entre dos nodos en un gráfico ponderado?

Una respuesta a cualquiera de las dos está bien, aunque me pregunto si una respuesta a la segunda pregunta se puede hacer de manera más eficiente que llama a una respuesta a la primera pregunta.k

Ensalada Realz
fuente
2
Una búsqueda de Google en "k rutas más cortas" arroja una serie de referencias que describen algoritmos para este problema. También hay un artículo de Wikipedia sobre exactamente este tema: en.wikipedia.org/wiki/K_shortest_path_routing
DW
@DW ¿Hacer una respuesta, con un breve resumen?
Raphael

Respuestas:

5

kkO(metro+norteIniciar sesiónnorte+k)k

Si no permite los ciclos, es posible que desee ver el algoritmo de Hershberger et al. [2]


[1] Eppstein, David. "Encontrar los k caminos más cortos". Revista SIAM sobre informática 28.2 (1998): 652-673. [ CiteSeerX ]

[2] Hershberger, John, Matthew Maxel y Subhash Suri. "Encontrar las k rutas más cortas y simples: un nuevo algoritmo y su implementación". Transacciones de ACM en Algoritmos (TALG) 3.4 (2007): 45. [ CiteSeerX ]

Juho
fuente