你能推荐任何实现 k-shortest 算法的 java 库 -> 寻找替代方法,而不是有向多图中唯一最短的方法吗?
我只发现了 JGraphT,但实际上存在错误(我已提交),但我想修复它需要很多时间,还有其他可用的实现吗?除了 JGraphT,我只发现了小型单人项目:/
或者很难修改 Disjktra 最短路径算法以显示替代路径?
谢谢
最佳答案
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 的也是一个很好的选择。
希望对您有所帮助。
关于java - k-最短(替代)路径算法,java实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12773525/