K-最短(二选一)路径算法,Java实现 [英] k-shortest (alternative) path algorithm, java implementations
问题描述
你能不能推荐任何Java库,实现了K-最短的算法 - >寻找替代方法,而不是针对多图唯一的最短
Could you recommend any java library which implements k-shortest algorithm -> searching for alternative ways, not the only shortest one in directed multigraph ?
我只找到JGraphT但实际上是错误(我提交的),但它会占用大量的时间来修复它,我想,还有没有其他可用的实现?除了JGraphT我发现只有小单人项目:/
I found only JGraphT but there is actually bug (which i submitted) but it will take a lot of time to fix it i guess, are there any other available implementations ? Except JGraphT i found only small one-man projects :/
或将是很难修改Disjktra最短路径ALG显示替换路径?
OR would be hard to modify Disjktra shortest path alg to show alternative paths ?
感谢
推荐答案
2种选择方式:
选项1. 类KshortestPath
的<一个href="http://www-sop.inria.fr/mascotte/mascopt/release/docs-1.2/mascoptLib-1.2/mascoptLib/algos/abstractalgos/KShortestPath.html"相对=nofollow>的MascOpt包是一个很好的选择,一个Java实现的K-最短路径。
Option 1. The class KshortestPath
from the MascOpt Package is a good option for a Java implementation of k-shortest paths.
选项2.你也可以试试这个从的 code.google.com 这似乎是一个人的努力,但好事是,该算法是共享:日元的排名 - 细节在这里(的 http://www.ohloh.net/p/k-shortest-paths )
Option 2. You can also try this from code.google.com This seems to be a one person's effort, but the good thing is that the algorithm is shared: Yen's Ranking - the details are here.(http://www.ohloh.net/p/k-shortest-paths)
注意:寻找在一个给定的图中的所有节点对之间的最短路径是不同的问题。请参阅本等质疑的Dijkstra与弗洛伊德 - 沃肖尔。
Note: Finding the shortest-paths between all pairs of nodes in a given graph is a different problem. See this SO question on Dijkstra vs. Floyd-Warshall.
另外请注意, K-最短路径
丰富的图形往往是(Dijkstra算法)最短路径的细微变化 - 最短路径略有上顶点之间的替代路径更高的成本。
Also note that k-shortest paths
for rich graphs tend to be slight variations of the (Dijkstra) shortest path - alternative paths between vertices on the shortest-path with slightly higher costs.
我知道的任择议定书要求的Java实现,但如果人们有一个选择,而R是一种选择,那么 kBestShortestPaths
的从CRAN包是一个非常好的选择,以及。
I know the OP asked for Java implementations but if people have a choice and R is an option, then the kBestShortestPaths
package from CRAN is a very good option as well.
希望有所帮助。
这篇关于K-最短(二选一)路径算法,Java实现的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!