Нахождение k-го кратчайшего пути?

Нахождение кратчайшего пути между двумя точками на графе - это классический вопрос алгоритмов с множеством хороших ответов ( алгоритм Дейкстры , Беллман-Форд ] и т. д.). Мой вопрос заключается в том, существует ли эффективный алгоритм, который при наличии ориентированного взвешенного графа, пары узлов s и t и значения k находит k-й кратчайший путь между s и t. В случае, если существует несколько путей одинаковой длины, которые связаны для k-го кратчайшего, алгоритм может вернуть любой из них.

Я подозреваю, что этот алгоритм, вероятно, может быть выполнен за полиномиальное время, хотя я Мне известно, что может быть сокращение от проблемы самого длинного пути , которое сделало бы его NP-трудным.

Кто-нибудь знает такой алгоритм или сокращение, которое показывает, что это NP- сложно?