Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

single_source_dijkstra

single_source_dijkstra(G, source, target=None, cutoff=None, weight='weight')[source]

Compute shortest paths and lengths in a weighted graph G.

Uses Dijkstra’s algorithm for shortest paths.

Parameters:

G : NetworkX graph

source : node label

Starting node for path

target : node label, optional

Ending node for path

cutoff : integer or float, optional

Depth to stop the search. Only paths of length <= cutoff are returned.

Returns:

distance,path : dictionaries

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.

Notes

Edge weight attributes must be numerical. Distances are calculated as sums of weighted edges traversed.

Based on the Python cookbook recipe (119466) at http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466

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.single_source_dijkstra(G,0)
>>> print(length[4])
4
>>> print(length)
{0: 0, 1: 1, 2: 2, 3: 3, 4: 4}
>>> path[4]
[0, 1, 2, 3, 4]