travel.py 文件源码

def dijkstra(vertices, teleport_edges, source):
    infinity = 10e50

    dist = {v: infinity for v in vertices}
    dist[source] = 0
    prev = {v: None for v in vertices}

    Q = []

    for v in vertices:
        heapq.heappush(Q, (dist[v], v))

    while Q:
        _, v = heapq.heappop(Q)
        for v2 in vertices:
            if v != v2:
                d = distance(v, v2, teleport_edges)
                if d is None:
                    continue

                if dist[v] + d < dist[v2]:
                    dist[v2] = dist[v] + d
                    prev[v2] = v
                    #decrease-key
                    for i, node in enumerate(Q):
                        if node[1] == v2:
                            Q[i] = (dist[v] + d, v2)
                            break
                    heapq.heapify(Q)
    return dist, prev