dijkstra.py 文件源码

def dijkstra(graph, s):
    n = len(graph.keys())
    dist = dict()
    Q = list()

    for v in graph:
        dist[v] = inf
    dist[s] = 0

    heappush(Q, (dist[s], s))

    while Q:
        d, u = heappop(Q)
        if d < dist[u]:
            dist[u] = d
        for v in graph[u]:
            if dist[v] > dist[u] + graph[u][v]:
                dist[v] = dist[u] + graph[u][v]
                heappush(Q, (dist[v], v))
    return dist