Encontrar el camino más corto entre dos puntos en un gráfico es una pregunta clásica de algoritmos con muchas buenas respuestas Algoritmo de Dijkstra, Bellman-Ford, etc.) Mi pregunta es si existe un algoritmo eficiente que, dado un gráfico ponderado dirigido, un par de nodos syt, y un valor k, encuentre la késima ruta más corta entre syt. En el caso de que haya múltiples rutas de la misma longitud que se unan para el k-más corto, está bien que el algoritmo devuelva cualquiera de ellas.

ospecho que este algoritmo probablemente se puede hacer en tiempo polinómico, aunque sé que podría haber una reducción de la problema del camino más largo eso lo haría NP-hard.

¿Alguien sabe de tal algoritmo, o de una reducción que muestre que es NP-hard?