NetworkX

Previous topic

networkx.all_pairs_dijkstra_path_length

Next topic

networkx.bidirectional_dijkstra

networkx.single_source_dijkstra

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

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

Distances are calculated as sums of weighted edges traversed. Edges must hold numerical values for Graph and DiGraphs.

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]