def shortest_path(graph, source):
    """
    Return the shortest path distance between source and all other nodes using Dijkstra's
    algorithm.
    
    @attention: All weights must be nonnegative.
    
    @see: shortest_path_bellman_ford

    @type  graph: graph, digraph
    @param graph: Graph.

    @type  source: node
    @param source: Node from which to start the search.

    @rtype:  tuple
    @return: A tuple containing two dictionaries, each keyed by target nodes.
        1. Shortest path spanning tree
        2. Shortest distance from given source to each target node
    Inaccessible target nodes do not appear in either dictionary.
    """
    # Initialization
    dist     = {source: 0}
    previous = {source: None}

    # This is a sorted queue of (dist, node) 2-tuples. The first item in the
    # queue is always either a finalized node that we can ignore or the node
    # with the smallest estimated distance from the source. Note that we will
    # not remove nodes from this list as they are finalized; we just ignore them
    # when they come up.
    q = [(0, source)]

    # The set of nodes for which we have final distances.
    finished = set()

    # Algorithm loop
    while len(q) > 0:
        du, u = q.pop(0)

        # Process reachable, remaining nodes from u
        if u not in finished:
            finished.add(u)
            for v in graph[u]:
                if v not in finished:
                    alt = du + graph.edge_weight((u, v))
                    if (v not in dist) or (alt < dist[v]):
                        dist[v] = alt
                        previous[v] = u
                        bisect.insort(q, (alt, v))

    return previous, dist
dataset/ETHPy150Open pmatiello/python-graph/core/pygraph/algorithms/minmax.py/shortest_path/original