python - 是否可以修改此代码以使优先级队列在 O(logn) 时间内减少其 key ？

Question

尝试用 python 编写 dijkstras。当我无法修改元组时，如何在 O(logn) 中实现减少键操作？

我正在编写一个片段来解决邻接表上的 dijkstras，并且需要一个优先级队列实现。我目前正在将 (priority, value) 的元组传递给 pq，因此 heapify 会为我处理推送和弹出。但是，我不能修改元组，所以我不能有效地降低任何项目的优先级并且必须弹出所有项目直到找到我需要的项目，然后将所有项目重新添加到 pq，这使得时间复杂度为 O(V^ 2).有没有办法修改此代码，以便 decreaseKey 操作在 O(logn) 时间内工作？最好不涉及类(class)。我不能用列表代替元组；否则它不会堆积

def decrease_key(pq, v, val):
    li = []
    u = heapq.heappop(pq)

    while u[1] is not v:
        li.append(u)
        u = heapq.heappop(pq)

    for l in li:
        heapq.heappush(pq, l)

    heapq.heappush(pq, (val, v))


def dijkstra(G, src, dist, V):

    for v in range(V):
        dist[v] = float('inf')
    dist[src] = 0

    pq = []

    for k, v in dist.items():
        pq.append((v, k))

    while pq:
        u = heapq.heappop(pq)[1]
        for v, w in G[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                decrease_key(pq, v, dist[v])

O(n^2) 与所需的 O(nlogn)

Answer 1

正如@DavidEisenstat 在评论中指出的那样，如果您只是将多条记录添加到堆中，则不需要 decrease_key。

您还需要跟踪从优先级队列中弹出的节点，因此您只能在第一次看到节点时对其进行处理。 (否则最坏情况的复杂度会增加)

最后，如果您避免将那些无限的成本插入堆，并且如果您只在实际降低成本时才插入一个新节点，那就太好了。总而言之，像这样:

def dijkstra(G, src, dist, V):

    for v in range(V):
        dist[v] = float('inf')
    dist[src] = 0

    pq = [(0,src)]
    seen = [False]*V

    while pq:
        u = heapq.heappop(pq)[1]
        if seen[u]:
            continue
        seen[u] = True
        for v, w in G[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush( pq, (dist[v],v) )