无向图dijkstra算法。给定起始节点,返回一个表,该表映射从a到每个节点的最短路径及其值
from heapq import heappush, heappop
def dijkstra(edges, start):
graph = {}
for (x, y, z) in edges:
# A: [('B', 6)]
graph[x] = graph.get(x, []) + [(y, z)]
graph[y] = graph.get(y, []) + [(x, z)] # undirected graph
table = {}
for v in graph:
table[v] = (float("inf"), None) # inf, no previous node
table[start] = (0, None)
stack = [(0, start)]
visited = []
while(stack != []):
fill, node = heappop(stack)
w = table[node][0]
if(node in visited):
continue
visited.append(node)
for (v, weight) in graph[node]:
cur_weight, prev = table[v]
if(cur_weight > weight + w):
table[v] = (weight + w, node)
cur_weight, prev = table[v]
heappush(stack, (cur_weight, v))
return table
edges = [['A', 'C', 1], ['C', 'E', 1], ['E', 'B', 1], ['A', 'B', 10]]
print(dijkstra(edges, 'A')) # outputs the correct table
上面的表的输出是正确的,但是对于非常大的输出,如(n=5000),它似乎失败了,我不确定为什么
将堆栈交换为minheap以防止出现评论中提到的测试用例
编辑:根据下面的评论对其进行了优化
相关问题 更多 >
编程相关推荐