k最短路径（备选路径）算法，Java实现

Question

请问您能推荐任何实现k短路径算法的Java库吗？这里的路径是指在有向多图中寻找替代路径，而不仅仅是最短路径。

我只找到了JGraphT，但实际上存在错误（我已经提交了），但我想修复它需要很长时间，还有其他可用的实现吗？除了JGraphT之外，我只发现了一些小型个人项目 :/

或者说，将Disjktra最短路径算法修改为显示替代路径会很困难吗？

谢谢

- Martin V.

---

你对 k 条最短的边不相交或节点不相交路径感兴趣吗？如果是第一种情况，可以研究最小费用最大流算法。 - IVlad

Answer 1

2个可能的选项:

选项1. MascOpt Package中的class KshortestPath是实现k最短路径的Java的好选择。

选项2. 您也可以尝试来自code.google.com的这个。这似乎是一个人的努力，但好的是算法是共享的: Yen's Ranking - 详细信息在此处(http://www.ohloh.net/p/k-shortest-paths)。

注意: 找到给定图中所有节点对之间的最短路径是不同的问题。请参见关于Dijkstra vs. Floyd-Warshall的此SO问题。

请注意，对于丰富图形的k-最短路径来说，往往是（Dijkstra）最短路径的轻微变体 - 在最短路径上的顶点之间具有略高成本的替代路径。

我知道OP要求的是Java实现，但如果人们可以选择并且R是一种选择，则CRAN的kBestShortestPaths package 也是一个非常好的选择。

希望有所帮助。

- Ram Narasimhan

---

我刚刚尝试了第二种选择：Yen算法，效果非常好！对于一个有大约400个节点和1000条链接的图形，执行时间从JGrapht实现的3000毫秒降至Yen算法实现的0.3毫秒。是的，从3000到0.3。这不是打字错误。 - gjain

Answer 2

寻找k条最短路径与寻找替代路径是相关但不完全相同的问题。良好的替代路径更加复杂。请参阅其他类似方法：

• k-最短路径
• Pareto最优性
• Plateau方法
• 惩罚法

在这里可以看到Plateau方法的示意图。

如果您能阅读德语，那么这个讲座也很好：

• 例如，优化时间或距离=>问题：缺少有趣的替代方案
• dijunct路径=>同样的问题
• k-最短路径=>问题：真正的替代方案可能不在前1000条路径中

第5页

因此直觉告诉我们：替代路径应该具有几乎相同的距离或时间，但应该有明显的不同之处。因此第一个想法是：找到一条最小化长度AND相似性的路径。问题是：可能存在局部绕路。

第6页

我们引入了第三个标准：局部最优性：每个短子路径都需要是最短路径。

- Karussell

Answer 3

之前有类似的请求，但是在StackOverflow上寻找所有路径。 使用DFS查找图中的所有路径

希望这可以帮到你，虽然没有给出确切的解决方案，但提供了更多的指导。

- Gigaquad