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

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

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