Fetch all alternatives path using Djikstra

Currently i am using GraphHopper for movement trip simulation and i am using just the core library.

My question is does GraphHopper can fetch all possible path from origin to destination? Because when i run the code below, it only return 2 from 3 expected paths.

For example:

from JKT-BGR to JKT-MRD, should generate following possible paths:
JKT-BGR -> JKT-CAW -> JKT-KML -> JKT-MRD
JKT-BGR -> JKT-KSI -> JKT-KML -> JKT-MRD
JKT-BGR -> JKT-KSI -> JKT-DPK -> JKT-MRD

my code:

public class GraphHopperTest {

static String stringify(Map<Integer, String> nodeMap, Path path) {
    String result = "";

    IntIndexedContainer vertexList = path.calcNodes();

    if (vertexList != null && !vertexList.isEmpty()) {
        for (int i = 0; i < vertexList.size(); i++) {
            result += nodeMap.get(vertexList.get(i));
            if (i != vertexList.size() - 1) {
                result = result + " -> ";
            }
        }
    }

    return result;
}

public static void main(String[] args) {
    final EncodingManager encodingManager = EncodingManager.create("car");
    final FlagEncoder carEncoder = encodingManager.getEncoder("car");
    Weighting defaultWeighting = new ShortestWeighting(carEncoder);

    Map<Integer, String> nodeMap = new HashMap<>();
    nodeMap.put(1, "JKT-BGR");
    nodeMap.put(2, "JKT-CAW");
    nodeMap.put(3, "JKT-DPK");
    nodeMap.put(4, "JKT-KML");
    nodeMap.put(5, "JKT-KSI");
    nodeMap.put(6, "JKT-MRD");

    GraphHopperStorage G = new GraphBuilder(encodingManager).create();
    G.edge(1, 2, 1, false);
    G.edge(1, 5, 1, false);
    G.edge(2, 4, 1, false);
    G.edge(5, 4, 1, false);
    G.edge(5, 3, 1, false);
    G.edge(4, 6, 1, false);
    G.edge(3, 6, 1, false);
    
    Set<IntIndexedContainer> uniquePaths = new HashSet<>();

    RoutingAlgorithm algo1 = new AlternativeRoute(G, defaultWeighting, TraversalMode.NODE_BASED);
    List<Path> paths1 = algo1.calcPaths(1, 6);

    System.out.println("GH - Traversal mode = NODE_BASED");
    for (Path p:paths1) {
        uniquePaths.add(p.calcNodes());
        System.out.println(stringify(nodeMap, p));
    }
}

}

No finding all possible (is this what you are looking for?) paths is not implemented and would also make no sense except for very small graphs. But you can certainly use the GraphHopper graph and write an algorithm that does this.

hi easbar, thanks for your reply. i mean all possible shortest paths. so, previously, i did some simulation using tool called NetworkX and python. it has a feature to fetch all possible shortest path using Djikstra. And i need to convert the logic in this simulation to our backend which is written in Java + GraphHopper but so far i just found AlternativeRoute class that return list of path. For this class, is there any possibility to set maximum number of paths returned.

What is your definition of ‘all possible shortest paths’? Do you mean finding the top 100 (or so) shortest paths? Finding all shortest paths is the same as all paths? Do you have a link to some documentation of the NetworkX feature you are talking about?

There are a few parameters in this algorithm that you can use to control the number of paths being found and it has a setMaxPaths method as well. However it is not trying to find all paths by any means, but rather tries to find a few good options that are sufficiently different from each other.

Thanks for your reply again.
Based on the graph example above, from JKT-BGR to JKT-MRD will give me 3 possible shortest paths because each path has same number of hops.

Do you mean finding the top 100 (or so) shortest paths?

Yes.

Do you have a link to some documentation of the NetworkX feature you are talking about?

https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.shortest_paths.generic.all_shortest_paths.html

Example in NetworkX:

all_shortest_path = nx.all_shortest_paths(G, source=origin.get_id(), \
                                 target=destination.get_id(), \
                                 weight='duration', method='dijkstra')
Powered by Discourse