查找两点之间的最短路径的图形与很多很好的答案（ Dijkstra算法 贝尔曼 - 福特等），我的问题是，是否有一个有效的算法是，给出一个指示，加权图中，一对节点s和t和的值k，认定s和t之间的第k-最短路径。倘若有相同的长度，所有并列第k-最短，它的优良的算法返回它们中的任何的多条路径。

Finding the shortest path between two points in a graph is a classic algorithms question with many good answers (Dijkstra's algorithm, Bellman-Ford, etc.) My question is whether there is an efficient algorithm that, given a directed, weighted graph, a pair of nodes s and t, and a value k, finds the kth-shortest path between s and t. In the event that there are multiple paths of the same length that all tie for the kth-shortest, it's fine for the algorithm to return any of them.

我怀疑这个算法大概可以在多项式时间内完成，但我知道，有可能是从最长减少路径问题这将使得NP难。

I suspect that this algorithm can probably be done in polynomial time, though I'm aware that there might be a reduction from the longest path problem that would make it NP-hard.

有谁知道这样的算法，即减少，显示这是一个NP难？

Does anyone know of such an algorithm, or of a reduction that show that it is NP-hard?

推荐答案

最好的（基本上优化）算法是由于Eppstein.

The best (and basically optimal) algorithm is due to Eppstein.