寻找图中两点之间的最短路径是一个经典的算法问题，有很多很好的答案(Dijkstra's algorithm、Bellman-Ford 等)图中，一对节点 s 和 t，以及一个值 k，找到 s 和 t 之间的第 k 条最短路径。如果有多条相同长度的路径都与第 k 个最短路径相关联，则算法可以返回其中任何一条路径。
我怀疑这个算法可能可以在多项式时间内完成，尽管我知道这可能比 longest path problem 有所减少。这将使它成为 NP-hard。
有谁知道这样的算法，或表明它是 NP-hard 的归约？
最佳答案
最好的(基本上是最优的)算法是由于 Eppstein .
关于algorithm - 寻找第 k 条最短路径？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7208720/