我的无向图 Dijkstra 算法有什么问题？

Question

无向图dijkstra算法。给定起始节点，return一个table映射从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

上面 table 的输出是正确的，但是对于像 (n = 5000) 这样的超大输出，它似乎失败了，我不确定为什么？

Answer 1

将堆栈交换到 minheap 以防止像评论中提到的那样的测试用例。

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 = set()
    while(stack != []):
        w, node = heappop(stack)
        if(node in visited):
            continue
    
        visited.add(node)
        for (v, weight) in graph[node]:
            
            
            cur_weight, prev = table[v]
            if(cur_weight > weight + w):
                table[v] = (weight + w, node)          
                heappush(stack, (weight + w, v))
            
    return table

编辑：根据下面的评论对其进行了优化

我的无向图 Dijkstra 算法有什么问题？

What is wrong with my Dijkstra algorithm for undirected graph?

python

dijkstra