java - k-最短(替代)路径算法，java实现

Question

你能推荐任何实现 k-shortest 算法的 java 库 -> 寻找替代方法，而不是有向多图中唯一最短的方法吗？

我只发现了 JGraphT，但实际上存在错误(我已提交)，但我想修复它需要很多时间，还有其他可用的实现吗？除了 JGraphT，我只发现了小型单人项目:/

或者很难修改 Disjktra 最短路径算法以显示替代路径？

谢谢

Answer 1

2 个可能的选项:

选项 1。类 KshortestPath 来自 the MascOpt Package是 k-最短路径的 Java 实现的一个很好的选择。

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

注意:寻找给定图中所有节点对之间的最短路径是一个不同的问题。在 Dijkstra vs. Floyd-Warshall 上查看此 SO 问题.

另请注意，富图的k-shortest paths 往往是 (Dijkstra) 最短路径的细微变化 - 最短路径上顶点之间的备选路径成本略高。

我知道 OP 要求 Java 实现，但如果人们有选择并且 R 是一个选项，那么 kBestShortestPaths package来自 CRAN 的也是一个很好的选择。

希望对您有所帮助。