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 d
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.
algorithms
graphs
shortest-path
graph-traversal
Ensalada Realz
fuente
fuente
Respuestas:
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 ]
fuente