Successively getting all shortest paths between two nodes (instead of only a single shortest path).
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.
YList allShortestPaths = new YList();
YCursor pathCursor = ShortestPaths.kShortestPathsCursor(graph, edgeCostsDP, startNode, endNode, Integer.MAX_VALUE);
if (pathCursor.ok())
{
final EdgeList firstPath = (EdgeList)pathCursor.current();
final double costsOfFirstPath = calculateCostsForPath(firstPath, edgeCostsDP);
allShortestPaths.add(firstPath);
pathCursor.next();
while (pathCursor.ok())
{
EdgeList currPath = (EdgeList)pathCursor.current();
double currCosts = calculateCostsForPath(currPath, edgeCostsDP);
if (!(currCosts > costsOfFirstPath))
{
allShortestPaths.add(currPath);
pathCursor.next();
}
else
break;
}
}
|
| Note |
|
The YCursor object returned by static method ShortestPaths.kShortestPathsCursor is a special "live" cursor implementation that calculates its result on demand.
|
See the Javadoc API description for class ShortestPaths
for more information on the yFiles library's shortest path algorithms.