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

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