是否可以修改此代码以使优先级队列在 O(logn) 时间内减少其密钥?
Can this code be modified to make the priority queue decrease its key in O(logn) time?
正在尝试在 python 中编写 dijkstras。当我无法修改元组时,如何在 O(logn) 中实现减少键操作?
我正在编写一个片段来解决邻接表上的 dijkstras,并且需要优先级队列实现。我目前正在将 (priority, value) 的元组传递给 pq,因此 heapify 会为我处理推送和弹出。但是,我不能修改元组,所以我不能有效地降低任何项目的优先级并且必须弹出所有项目直到找到我需要的项目,然后将所有项目重新添加到 pq,这使得时间复杂度为 O(V^ 2).有没有办法修改此代码,以便 decreaseKey 操作在 O(logn) 时间内工作?最好不涉及 类。我不能用列表代替元组;否则它不会堆积
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)
正如@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}')
正在尝试在 python 中编写 dijkstras。当我无法修改元组时,如何在 O(logn) 中实现减少键操作?
我正在编写一个片段来解决邻接表上的 dijkstras,并且需要优先级队列实现。我目前正在将 (priority, value) 的元组传递给 pq,因此 heapify 会为我处理推送和弹出。但是,我不能修改元组,所以我不能有效地降低任何项目的优先级并且必须弹出所有项目直到找到我需要的项目,然后将所有项目重新添加到 pq,这使得时间复杂度为 O(V^ 2).有没有办法修改此代码,以便 decreaseKey 操作在 O(logn) 时间内工作?最好不涉及 类。我不能用列表代替元组;否则它不会堆积
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)
正如@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}')