您能否推荐任何实现 k-shortest 算法的 java 库 -> 寻找替代方法,而不是有向多重图中唯一最短的方法?
我只发现了 JGraphT 但实际上存在错误(我提交了)但我想修复它需要很多时间,还有其他可用的实现吗?除了 JGraphT,我只发现了小型单人项目:/
或者很难修改 Disjktra 最短路径算法以显示替代路径?
谢谢
您能否推荐任何实现 k-shortest 算法的 java 库 -> 寻找替代方法,而不是有向多重图中唯一最短的方法?
我只发现了 JGraphT 但实际上存在错误(我提交了)但我想修复它需要很多时间,还有其他可用的实现吗?除了 JGraphT,我只发现了小型单人项目:/
或者很难修改 Disjktra 最短路径算法以显示替代路径?
谢谢
2个可能的选项:
选项 1。class KshortestPath
来自MascOpt 包的 Java 实现 k 最短路径是一个不错的选择。
选项 2。您也可以从code.google.com尝试这个 这似乎是一个人的努力,但好在算法是共享的:日元排名 - 详细信息在这里。(http://www.ohloh .net/p/k-最短路径)
注意:在给定图中找到所有节点对之间的最短路径是一个不同的问题。请参阅有关Dijkstra 与 Floyd-Warshall 的这个 SO 问题。
另请注意,k-shortest paths
对于丰富的图,往往是(Dijkstra)最短路径的轻微变化 - 最短路径上的顶点之间的替代路径,成本略高。
我知道 OP 要求 Java 实现,但如果人们可以选择并且 R 是一个选项,那么来自 CRAN 的kBestShortestPaths
包也是一个非常好的选择。
希望有帮助。
找到 k 最短路径是相关的,但与替代路径的问题并不完全相同。好的替代路径更复杂。阅读其他类似方法的概述:
高原方法在这里有点说明。
如果您可以阅读德语,那么这个讲座很好:
第 5 页
所以直觉告诉我们:另一种选择应该有几乎相同的距离或时间。但应该有很大不同。所以第一个想法:找到一条最小化长度和相似性的路径。问题:可能存在局部弯路。
第 6 页
我们引入第三个标准:局部最优性:每个短子路径都需要是最短路径。
之前也有过类似的请求,不过是在 StackOverflow 上寻找所有的路径。 使用 DFS 查找图中的所有路径
希望这会有所帮助,它得到了回答,但不是确切的解决方案,而是更多的指南