Dijkstra’s algorithm for shortest paths using bidirectional search.
Returns a tuple of two dictionaries keyed by node. The first dicdtionary stores distance from the source. The second stores the path from the source to that node.
Raise an exception if no path exists.
| Parameters: | G : NetworkX graph source : node label
target : node label
|
|---|
Notes
Distances are calculated as sums of weighted edges traversed.
Edges must hold numerical values for Graph and DiGraphs.
In practice bidirectional Dijkstra is much more than twice as fast as ordinary Dijkstra.
Ordinary Dijkstra expands nodes in a sphere-like manner from the source. The radius of this sphere will eventually be the length of the shortest path. Bidirectional Dijkstra will expand nodes from both the source and the target, making two spheres of half this radius. Volume of the first sphere is pi*r*r while the others are 2*pi*r/2*r/2, making up half the volume.
This algorithm is not guaranteed to work if edge weights are negative or are floating point numbers (overflows and roundoff errors can cause problems).
Examples
>>> G=nx.path_graph(5)
>>> length,path=nx.bidirectional_dijkstra(G,0,4)
>>> print length
4
>>> print path
[0, 1, 2, 3, 4]