尝试用python编写dijkstras。当我无法修改我的元组时，如何在O（logn）中实现减少键操作？
我正在编写一个片段来解决邻接列表上的dijkstras并需要一个优先级队列实现。我目前正在将一个元组（优先级，值）传递给pq，以便heapify为我处理推送和弹出。然而，我不能修改元组，因此我不能有效地降低任何项目的优先级，并且必须弹出所有项目，直到找到我需要的项目，然后将所有项目读取到pq，这使得时间复杂度为O（V^2）。有什么方法可以修改此代码，以便decreseKey操作在O（logn）时间内工作？最好不涉及类。我不能使用列表而不是元组；否则它不会heapify
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）vs所需的O（n^2）
正如@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) )
已经有一段时间了，但我认为堆的重点是保留最小距离节点的队列，以重新计算和更新您的距离。
import heapq
def dijkstra(graph, src):
# Read all graph nodes
nodes = list(graph.keys())
# Initialize all distances to infinity and build a queue of unvisted nodes
dist = {}
pq = []
for node in nodes:
dist[node] = float('inf')
dist[src] = 0
heapq.heappush(pq, (0, src))
# While shorter distances to nodes, recalculate neighbor distances
while pq:
src_dist, unvisited_node = heapq.heappop(pq)
# Recalculate total distance for each neighbor
unvisted_neighbors = graph.get(unvisited_node, [])
for n_node, n_dist in unvisted_neighbors:
test_dist = src_dist + n_dist
# If test distance is shorted, update and enqueue
if test_dist < dist[n_node]:
dist[n_node] = test_dist
heapq.heappush(pq, (test_dist, n_node))
return dist
test_graph = {
'a': (('b', 7), ('c', 9), ('f', 14)),
'b': (('a', 7), ('d', 15), ('c', 10)),
'c': (('a', 9), ('b', 10), ('d', 11), ('f', 2)),
'd': (('b', 15), ('c', 11), ('e', 6)),
'e': (('d', 6), ('f', 9)),
'f': (('c', 2), ('e', 9))
}
'''Lazy graph structure.
key: source node name
value: adjacent node name and distance pairs
https://www.bogotobogo.com/python/images/Graph/graph_diagram.png
'''
src_node = 'e'
d = dijkstra(test_graph, src_node)
for k, v in d.items():
print(f'{src_node}->{k}: {v}')
