Localizando o caminho k-menor entre dois nós

Dado um dígrafo ponderado e uma função de peso , normalmente é possível usar o algoritmo de Dijkstra para obter o caminho mais curto. O que me interessa é como obter o caminho mais curto curto e assim por diante.$G=V,E$$d(u,v)$$2^{nd}$$3^{rd}$

Questões:

Existe um algoritmo eficiente para obter o i-ésimo caminho mais curto entre dois nós em um gráfico ponderado?

Existe um algoritmo eficiente para obter os caminhos mais curtos entre dois nós em um gráfico ponderado?

Uma resposta para qualquer uma delas é boa, embora eu queira saber se uma resposta para a segunda pergunta pode ser feita com mais eficiência do que chama para uma resposta para a primeira pergunta.$k$

$k$$k$$O(m+n \log n + k)$$k$

Se você não permitir ciclos, talvez queira examinar o algoritmo de Hershberger et al. [2]

[1] Eppstein, David. "Encontrando os k caminhos mais curtos." SIAM Journal on computing 28.2 (1998): 652-673. [ CiteSeerX ]

[2] Hershberger, John, Matthew Maxel e Subhash Suri. "Encontrando os k caminhos mais curtos e simples: um novo algoritmo e sua implementação." Transações ACM em algoritmos (TALG) 3.4 (2007): 45. [ CiteSeerX ]