Dijkstra's algorithm for shortest paths using bidirectional search. Returns a twotuple (d,p) where d is the distance and p is the path from the source to the target. Distances are calculated as sums of weighted edges traversed. Edges must hold numerical values for XGraph and XDiGraphs. The weights are set to 1 for Graphs and DiGraphs. In practice bidirectional Dijkstra is much more than twice as fast as ordinary Dijkstra. Ordinary Dijkstra expands nodes in a spherelike manner from the source. The radius of this sphere will eventually be the length of the shortest path. Bidirectional Dijkstra will expand nodes from both the source and the target, making two spheres of half this radius. Volume of the first sphere is pi*r*r while the others are 2*pi*r/2*r/2, making up half the volume. This algorithm is not guaranteed to work if edge weights are negative or are floating point numbers (overflows and roundoff errors can cause problems). Definition at line 350 of file paths.py. 00350 : """ Dijkstra's algorithm for shortest paths using bidirectional search. Returns a twotuple (d,p) where d is the distance and p is the path from the source to the target. Distances are calculated as sums of weighted edges traversed. Edges must hold numerical values for XGraph and XDiGraphs. The weights are set to 1 for Graphs and DiGraphs. In practice bidirectional Dijkstra is much more than twice as fast as ordinary Dijkstra. Ordinary Dijkstra expands nodes in a spherelike manner from the source. The radius of this sphere will eventually be the length of the shortest path. Bidirectional Dijkstra will expand nodes from both the source and the target, making two spheres of half this radius. Volume of the first sphere is pi*r*r while the others are 2*pi*r/2*r/2, making up half the volume. This algorithm is not guaranteed to work if edge weights are negative or are floating point numbers (overflows and roundoff errors can cause problems). """ if source is None or target is None: raise NetworkXException( "Bidirectional Dijkstra called with no source or target") if source == target: return (0, [source]) #Init: Forward Backward dists = [{}, {}]# dictionary of final distances paths = [{source:[source]}, {target:[target]}] # dictionary of paths fringe = [[], []] #heap of (distance, node) tuples for extracting next node to expand seen = [{source:0}, {target:0} ]#dictionary of distances to nodes seen #initialize fringe heap heapq.heappush(fringe[0], (0, source)) heapq.heappush(fringe[1], (0, target)) #neighs for extracting correct neighbor information if G.is_directed(): neighs = [G.successors_iter, G.predecessors_iter] else: neighs = [G.neighbors_iter, G.neighbors_iter] #variables to hold shortest discovered path #finaldist = 1e30000 finalpath = [] # if unweighted graph, set the weights to 1 on edges by # introducing a get_edge method if not hasattr(G,"get_edge"): G.get_edge=lambda x,y:1 dir = 1 while fringe[0] and fringe[1]: # choose direction # dir == 0 is forward direction and dir == 1 is back dir = 1dir # extract closest to expand (dist, v )= heapq.heappop(fringe[dir]) if v in dists[dir]: # Shortest path to v has already been found continue # update distance dists[dir][v] = dist #equal to seen[dir][v] if v in dists[1dir]: # if we have scanned v in both directions we are done # we have now discovered the shortest path return (finaldist,finalpath) for w in neighs[dir](v): if(dir==0): #forward vwLength = dists[dir][v] + G.get_edge(v,w) else: #back, must remember to change v,w>w,v vwLength = dists[dir][v] + G.get_edge(w,v) if w in dists[dir]: if vwLength < dists[dir][w]: raise ValueError,\ "Contradictory paths found: negative weights?" elif w not in seen[dir] or vwLength < seen[dir][w]: # relaxing seen[dir][w] = vwLength heapq.heappush(fringe[dir], (vwLength,w)) paths[dir][w] = paths[dir][v]+[w] if w in seen[0] and w in seen[1]: #see if this path is better than than the already #discovered shortest path totaldist = seen[0][w] + seen[1][w] if finalpath == [] or finaldist > totaldist: finaldist = totaldist revpath = paths[1][w][:] revpath.reverse() finalpath = paths[0][w] + revpath[1:] return False #def dijkstra(G,source,target): # return bidirectional_dijkstra(G,source,target) def single_source_dijkstra_path(G,source):
