# dijkstra

Jan 30th, 2021
596
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. inf = float("inf")
2.
3. def createGraph(n):
4.     M = []
5.     for i in range(n):
6.         M.append([])
7.         for j in range(n):
8.             M[i].append(inf)
9.     return M
10.
11.
12. def size(G):
13.     return len(G)
14.
15.
16. def insert(G, i, j, w):
17.     G[i][j] = w
18.
19.
20. def delete(G, i, j):
21.     G[i][j] = inf
22.
23.
24. def isEdge(G, i, j):
25.     return G[i][j] != []
26.
27.
28. def weight(G, i, j):
29.     return G[i][j]
30.
31.
32. def getAdjacents(G, i):
33.     V = []
34.     for j in range(len(G)):
35.         if G[i][j] != inf:
36.             V.append([j, G[i][j]])
37.     return V
38.
39.
40. def minVertex(D, V):
41.     min = inf
42.     y = -1
43.     for i in range(len(D)):
44.         if (not V[i]) and (D[i] < min):
45.             y = i
46.             min = D[i]
47.     return y
48.
49.
50. def Dijkstra(G, s):
51.     n = size(G)
52.
53.     dist = []
54.     visited = []
55.
56.     for i in range(n):
57.         dist.append(inf)
58.         visited.append(False)
59.
60.     dist[s] = 0
61.
62.     for i in range(n - 1):
63.         next = minVertex(dist, visited)
64.         visited[next] = True
65.
66.         V = getAdjacents(G, next)
67.         for [z, w] in V:
68.             d = dist[next] + w
69.             if dist[z] > d:
70.                 dist[z] = d
71.
72.     return dist
73.
74.
75. ########################
76.
77. G = createGraph(6)
78.
79. insert(G, 0, 1, 2)
80. insert(G, 0, 5, 9)
81. insert(G, 1, 3, 8)
82. insert(G, 1, 2, 6)
83. insert(G, 1, 5, 5)
84. insert(G, 2, 3, 1)
85. insert(G, 4, 3, 3)
86. insert(G, 4, 2, 7)
87. insert(G, 5, 4, 3)
88.
89.
90. D = Dijkstra(G, 0)
91. print("")
92. print(D[0])
93. print(D[1])
94.
95.
96.
97.
RAW Paste Data