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' Definition at line 481 of file paths.py. 00481 : """ 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' """ if source==target: return (0, [source]) dist = {} # dictionary of final distances paths = {source:[source]} # dictionary of paths seen = {source:0} fringe=[] # use heapq with (distance,label) tuples heapq.heappush(fringe,(0,source)) if not G.is_directed(): G.successors=G.neighbors # if unweighted graph, set the weights to 1 on edges by # introducing a get_edge method # NB: for the weighted graphs (XGraph,XDiGraph), the data # on the edge (returned by get_edge) must be numerical if not hasattr(G,"get_edge"): G.get_edge=lambda x,y:1 while fringe: (d,v)=heapq.heappop(fringe) if v in dist: continue # already searched this node. dist[v] = seen[v] if v == target: break for w in G.successors(v): vw_dist = dist[v] + G.get_edge(v,w) if w in dist: if vw_dist < dist[w]: raise ValueError,\ "Contradictory paths found: negative weights?" elif w not in seen or vw_dist < seen[w]: seen[w] = vw_dist heapq.heappush(fringe,(vw_dist,w)) paths[w] = paths[v]+[w] return (dist,paths) def floyd_warshall(graph):
