boris-vlasenko

Алгоритм Дейкстры

Oct 1st, 2020
894
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def D(node,a):
  2.     q = [node]
  3.     N = len(a)
  4.     visited = []
  5.     res = {}
  6.     res[node] = 0
  7.     while q:
  8.         node = q.pop()
  9.         visited.append(node)
  10.         new_q = []
  11.         for c in range(N):
  12.             if a[node][c] != 0:
  13.                 if c not in visited:
  14.                     new_q.append(c)
  15.                 if c in res:
  16.                     res[c] = min(res[c],res[node]+a[node][c])
  17.                 else:
  18.                     res[c] = res[node] + a[node][c]
  19.         q = new_q
  20.         new_q = []
  21.     return res
  22.  
  23. a = []
  24. a.append([0,7,9,0,0,14])
  25. a.append([7,0,10,15,0,0])
  26. a.append([9,10,0,11,0,2])
  27. a.append([0,15,11,0,6,0])
  28. a.append([0,0,0,6,0,9])
  29. a.append([14,0,2,0,9,0])
  30.  
  31. a1 = 0
  32. a2 = 1
  33. w= D(a1,a)
  34. for x in w:
  35.     print(x+1,w[x])
  36.  
  37.  
  38.  
RAW Paste Data