Shortest path algorithms with Java

[DEX graphdb]

Since 4.5 DEX includes shortest path algorithms for Java (see old blog announcement: http://sparsity-technologies.com/blog/?p=540).

Here is an example of use for Java:

First, remember to include in your code the algorithms package by adding:

import com.sparsity.dex.algorithms.SinglePairShortestPathDijkstra;
import com.sparsity.dex.algorithms.SinglePairShortestPathBFS;

We assume here, that you already have a created db with nodes and edges included.

If you do not have weights in your edges you should perform a BFS (More info: http://en.wikipedia.org/wiki/Breadth-first_search):

        System.out.println("SinglePairShortestPath BFS");
        // Create a new unweighted shortest path from "startingNode" to "endingNode"
        SinglePairShortestPathBFS spBFS = new SinglePairShortestPathBFS(sess, startingNode, endingNode);
        // Allow the use of all the edge types in Any direction
        spBFS.addAllEdgeTypes(EdgesDirection.Any);
        // Allow the use of all the node types
        spBFS.addAllNodeTypes();
        // Calculate the shortest path
        spBFS.run();
   // Check the path if it exists
        if (spBFS.exists())
        {
            // Get the total path cost
            System.out.println("A shortest path exists with cost: "+spBFS.getCost()+".");
            // Get the path
            OIDList pathAsNodes = spBFS.getPathAsNodes();
            OIDListIterator pathIt = pathAsNodes.iterator();
            while (pathIt.hasNext())
            {
                long nodeid = pathIt.next();
                System.out.println("Node: "+nodeid);
            }
        }
        else
        {
            System.out.println("No path found");
        }
        // Close the shortest path
        spBFS.close();

But if you wish to consider the weights in the edges to find the shortest path you should consider using Dijkstra (More about Dijkstra: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) :

        System.out.println("SinglePairShortestPath Dijkstra");
        // Create a new weighted shortest path from "startingNode" to "endingNode"
        SinglePairShortestPathDijkstra spDijkstra = new SinglePairShortestPathDijkstra(sess, startingNode, endingNode);
        // Allow the user of the edge type "anEdgeType" in outgoing direction and using "edgeWeight" as the edge weight attribute
        spDijkstra.addWeightedEdgeType(anEdgeType, EdgesDirection.Outgoing, edgeWeight);
        // Allow the use of all the node types
        spDijkstra.addAllNodeTypes();
        // Calculate the shortest path
        spDijkstra.run();
   // Check the path if it exists
        if (spDijkstra.exists())
        {
            // Get the total path cost
            System.out.println("A shortest path exists with cost: "+spDijkstra.getCost()+".");
            // Get the path
            OIDList pathAsNodes = spDijkstra.getPathAsNodes();
            OIDListIterator pathIt = pathAsNodes.iterator();
            while (pathIt.hasNext())
            {
                long nodeid = pathIt.next();
                System.out.println("Node: "+nodeid);
            }
        }
        else
        {
            System.out.println("No path found");
        }
        // Close the shortest path
        spDijkstra.close();