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]