Document

_bidirectional_dijkstra(G, source, target, weight='weight', ignore_nodes=None, ignore_edges=None)

This function returns the shortest path between source and target ignoring nodes and edges in the containers ignore_nodes and ignore_edges.

This is a custom modification of the standard Dijkstra bidirectional shortest path implementation at networkx.algorithms.weighted

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

Parameters

G : NetworkX graph
source : node: Starting node.
target : node: Ending node.
weight: string, function, optional (default='weight') :: Edge data key or weight function corresponding to the edge weight
ignore_nodes : container of nodes: nodes to ignore, optional
ignore_edges : container of edges: edges to ignore, optional

Raises

NetworkXNoPath: If no path exists between source and target.

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.

Dijkstra's algorithm for shortest paths using bidirectional search.

Examples

See :

Local connectivity graph

Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.

Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)

SVG is more flexible but power hungry; and does not scale well to 50 + nodes.

All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them