Dijkstra’s algorithm for shortest paths in a weighted graph G.
Use:
single_source_dijkstra_path() - shortest path list of nodes
single_source_dijkstra_path_length() - shortest path length
Returns a tuple of two dictionaries keyed by node. The first stores distance from the source. The second stores the path from the source to that node.
Distances are calculated as sums of weighted edges traversed. Edges must hold numerical values for XGraph and XDiGraphs. The weights are 1 for Graphs and DiGraphs.
Optional target argument stops the search when target is found.
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).
See also ‘bidirectional_dijkstra_path’