Warning
This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.
bidirectional_dijkstra¶
- bidirectional_dijkstra(G, source, target, weight='weight')[source]¶
Dijkstra’s algorithm for shortest paths using bidirectional search.
Parameters : G : NetworkX graph
source : node
Starting node.
target : node
Ending node.
weight: string, optional (default=’weight’)
Edge data key corresponding to the edge weight
Returns : length : number
Shortest path length.
Returns a tuple of two dictionaries keyed by node.
The first dictionary stores distance from the source.
The second stores the path from the source to that node.
Raises : NetworkXNoPath
If no path exists between source and target.
See also
shortest_path, shortest_path_length
Notes
Edge weight attributes must be numerical. Distances are calculated as sums of weighted edges traversed.
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]