在 Floyd-Warshall 算法中，计算任意一对顶点的最短路径成本。额外的簿记使我们能够将实际路径(顶点列表)保持在最短路径上。
我如何扩展 Floyd-Warshall 以便对于任何一对顶点，都能找到前 K 条最短路径？例如，对于 K=3，结果将是计算并维护 3 条最短路径？
我一直在使用 Java implementation来自塞奇威克。
最佳答案
听起来更像是 Dijkstra 更容易修改以返回 N 条最短路径。允许搜索进入顶点，直到K个最短备选方案进入顶点。
更多信息您可以查看wikipedia article
关于algorithm - 弗洛伊德·沃肖尔 : computing top-k shortest paths per vertex pair，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25455288/