1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| def dijkstra(E, n0):
v_size = len(E)
l=[1e5]*v_size
l[n0]=0
s = [n0]
s_hat = [i for i in range(v_size)]
s_hat.remove(n0)
parent = [-1]*v_size
while s_hat:
d = 1e5
index_u, index_v = -1, -1
for u in s:
for v in s_hat:
d_uv = l[u]+E[u][v]
if d > d_uv:
d = d_uv
index_u = u
index_v = v
l[index_v]=d
parent[index_v] = index_u
s.append(index_v)
s_hat.remove(index_v)
print('next')
print(s, s_hat)
print(l, d, index_v)
print(index_u, index_v)
return l, parent
if __name__=='__main__':
E = [[0,5,2,1e5],[5,0,7,3],[2,7,0,1],[1e5,3,1,0]]
l,p = dijkstra(E,1)
print(l, p)
next
[1, 3] [0, 2]
[100000.0, 0, 100000.0, 3] 3 3
1 3
next
[1, 3, 2] [0]
[100000.0, 0, 4, 3] 4 2
3 2
next
[1, 3, 2, 0] []
[5, 0, 4, 3] 5 0
1 0
[5, 0, 4, 3] [1, -1, 3, 1]
|