How to Compute All Shortest Paths Between Two Nodes

Commonly, any standard algorithms that solve the shortest path problem between two nodes return a single shortest path only.

Starting with yFiles version 2.3, method ShortestPaths.kShortestPathsCursor(y.base.Graph, y.base.DataProvider, y.base.Node, y.base.Node, int) can be used to successively return all possible shortest paths between two nodes. The static method finds the first k paths (where k is given by the last parameter) connecting a pair of nodes in a directed graph and having least costs. It returns a special YCursor object to iterate over these paths in a suitable fashion.

To get hold of all proper shortest paths, the returned cursor can be used to iterate over the k paths until a path is returned with costs larger than the first one (which is a proper shortest path). This technique is demonstrated in the sample code fragment below.
What the sample code does:

• First, intitializes the static method to return an unbound number of shortest paths between the two nodes.
• Then uses the costs of the first returned path as an indicator and iterates over the remaining paths until the costs of the current path exceed those of the first.
• Stores each proper shortest path encountered into a list.

// To hold an edge list for every path. 
YList allShortestPaths = new YList();

// The actual number of proper shortest paths is unknown, so we start with a really great value for 'k'. 
YCursor pathCursor = ShortestPaths.kShortestPathsCursor(graph, edgeCostsDP, startNode, endNode, Integer.MAX_VALUE);
if (pathCursor.ok())
{
  // The first path between the two nodes having least costs. 
  final EdgeList firstPath = (EdgeList)pathCursor.current();
  final double costsOfFirstPath = calculateCostsForPath(firstPath, edgeCostsDP);

  allShortestPaths.add(firstPath);
  pathCursor.next();

  // Look further. 
  while (pathCursor.ok())
  {
    EdgeList currPath = (EdgeList)pathCursor.current();
    double currCosts = calculateCostsForPath(currPath, edgeCostsDP);
    // If the current path is also a proper shortest path with costs equal to those 
    // of the first path, then add it to the list. 
    if (!(currCosts > costsOfFirstPath))
    {
      allShortestPaths.add(currPath);
      pathCursor.next();
    }
    else
      break;
  }
}

See the Javadoc API description for class ShortestPaths for more information on the yFiles library's shortest path algorithms.