k-shortest(替代)路径算法,java实现

Question

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

我发现只有JGraphT,但实际上有bug(我提交了)但是我需要花很多时间修复它,是否有其他可用的实现？除了JGraphT,我发现只有小型单人项目:/

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

谢谢

Answer 1

2个可能的选择:

选项1. class KshortestPath来自MascOpt包的是k- shortest路径的Java实现的一个很好的选择.

选项2.你也可以从code.google.com尝试这个. 这似乎是一个人的努力,但好的是该算法是共享的:Yen的排名 - 详情在这里.(http://www.ohloh .net/p/k-shortest-paths)

注意:查找给定图形中所有节点对之间的最短路径是一个不同的问题.在Dijkstra对阵Floyd-Warshall看到这个问题.

另请注意,k-shortest paths对于富图,往往是(Dijkstra)最短路径的微小变化 - 最短路径上的顶点之间的替代路径,成本略高.

我知道OP要求Java实现,但是如果人们有选择而R是一个选项,那么来自CRAN 的kBestShortestPaths 包也是一个非常好的选择.

希望有所帮助.