Function dijkstra_shortest_paths

pattern/graph/__init__.py:810–837

Dijkstra algorithm for finding the shortest paths from the given node to all other nodes. Returns a dictionary of node id's, each linking to a list of node id's (i.e., the path).

(graph, id, heuristic=None, directed=False)

                heappush(q, (cost1 + cost2, n2, path))

def dijkstra_shortest_paths(graph, id, heuristic=None, directed=False):
    """ Dijkstra algorithm for finding the shortest paths from the given node to all other nodes.
        Returns a dictionary of node id's, each linking to a list of node id's (i.e., the path).
    """
    # Based on: Dijkstra's algorithm for shortest paths modified from Eppstein.
    # Based on: NetworkX 1.4.1: Aric Hagberg, Dan Schult and Pieter Swart.
    # This is 5x faster than:
    # for n in g: dijkstra_shortest_path(g, id, n.id)
    W = adjacency(graph, directed=directed, heuristic=heuristic)
    Q = [] # Use Q as a heap with (distance, node id)-tuples.
    D = {} # Dictionary of final distances.
    P = {} # Dictionary of paths.
    P[id] = [id] 
    seen = {id: 0} 
    heappush(Q, (0, id))
    while Q:
        (dist, v) = heappop(Q)
        if v in D: continue
        D[v] = dist
        for w in W[v].iterkeys():
            vw_dist = D[v] + W[v][w]
            if w not in D and (w not in seen or vw_dist < seen[w]):
                seen[w] = vw_dist
                heappush(Q, (vw_dist, w))
                P[w] = P[v] + [w]
    for n in graph:
        if n not in P: P[n]=None
    return P

def floyd_warshall_all_pairs_distance(graph, heuristic=None, directed=False):
    """ Floyd-Warshall&#x27;s algorithm for finding the path length for all pairs for nodes.