有人可以检测到在这段代码中使用python实现dijkstra算法的错误吗？

Question

我想实现dijkstra的算法（在无向图上）找到最短路径，我的代码是这样的。

注意：我没有使用堆/优先级队列或任何东西，但邻接列表，字典存储权重和布尔表，以避免在循环/递归循环永远。此外，该算法适用于大多数的测试案例，但未能为这个特殊的位置：https://ideone.com/iBAT0q

重要：图形可以从V1到V2（反之亦然），你必须使用最小重量有多个边缘。

import sys 

sys.setrecursionlimit(10000) 

def findMin(n): 
    for i in x[n]: 
     cost[n] = min(cost[n],cost[i]+w[(n,i)]) 
def dik(s): 
    for i in x[s]: 
     if done[i]: 
      findMin(i) 
      done[i] = False 
      dik(i) 
    return 
q = int(input()) 
for _ in range(q): 
    n,e = map(int,input().split()) 
    x = [[] for _ in range(n)] 
    done = [True]*n 
    w = {} 
    cost = [1000000000000000000]*n 
    for k in range(e): 
     i,j,c = map(int,input().split()) 
     x[i-1].append(j-1) 
     x[j-1].append(i-1) 
     try:          #Avoiding multiple edges 
      w[(i-1,j-1)] = min(c,w[(i-1,j-1)]) 
      w[(j-1,i-1)] = w[(i-1,j-1)] 
     except: 
      try: 
       w[(i-1,j-1)] = min(c,w[(j-1,i-1)]) 
       w[(j-1,i-1)] = w[(i-1,j-1)] 
      except: 
       w[(j-1,i-1)] = c 
       w[(i-1,j-1)] = c 
    src = int(input())-1 
    #for i in sorted(w.keys()): 
    # print(i,w[i]) 
    done[src] = False 
    cost[src] = 0 
    dik(src)   #First iteration assigns possible minimum to all nodes 
    done = [True]*n  
    dik(src)   #Second iteration to ensure they are minimum 
    for val in cost: 
     if val == 1000000000000000000: 
      print(-1,end=' ') 
      continue 
     if val!=0: 
      print(val,end=' ') 
    print() 

Answer 1

在第二遍中并不总能找到最佳值。如果您在示例中添加了第三遍，则会更接近预期结果，并且在第四次迭代之后，您就在那里。

你可以重复，直到不再更改的成本阵列制造：通过一团糟的代码去

done[src] = False 
cost[src] = 0 
dik(src) 

while True: 
    ocost = list(cost)   # copy for comparison 
    done = [True]*n  
    dik(src) 
    if cost == ocost: 
     break