Search code examples
javaalgorithmgraphmathematical-optimizationshortest-path

k-shortest (alternative) path algorithm, java implementations

Could you recommend any java library which implements k-shortest algorithm -> searching for alternative ways, not the only shortest one in directed multigraph ?

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 :/

OR would be hard to modify Disjktra shortest path alg to show alternative paths ?

Thanks

Solution

  • 2 Possible Options:

    Option 1. The class KshortestPath from the MascOpt Package is a good option for a Java implementation of 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)

    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.

    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.

    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.

    Hope that helps.