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.

Examples

>>> G=nx.path_graph(5)
>>> length,path=nx.bidirectional_dijkstra(G,0,4)
>>> print(length)
4
>>> print(path)
[0, 1, 2, 3, 4]

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).