Logo Search packages:      
Sourcecode: python-networkx version File versions  Download package

def networkx::paths::single_source_dijkstra (   G,
  source,
  target = None 
)

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):


Generated by  Doxygen 1.6.0   Back to index