Index
Help
Created with Snap
Created with Snap
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
4x
.25x
.5x
1x
2x
4x
?
s = PickSource()
t = PickSink()
dist[s] = 0
PQ.Insert(s,dist[s])
v = PQ.DeleteMin()
while
v != t:
for
w
in
Neighborhood(v):
if
dist[w] == gInfinity:
pred[w] = v
dist[w] = dist[v] + length[(v,w)]
PQ.Insert(w,dist[w])
elif
dist[w] > dist[v] + length[(v,w)]:
pred[w] = v
dist[w] = dist[v] + length[(v,w)]
PQ.DecreaseKey(w,dist[w])
v = PQ.DeleteMin()
ShowPath(s,t)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Edge (1,5) length: 108
Edge (1,26) length: 178
Edge (3,2) length: 158
Edge (3,6) length: 141
Edge (3,14) length: 138
Edge (3,28) length: 104
Edge (4,3) length: 125
Edge (4,12) length: 131
Edge (5,2) length: 119
Edge (5,3) length: 195
Edge (5,4) length: 158
Edge (5,26) length: 115
Edge (7,6) length: 133
Edge (7,8) length: 138
Edge (7,20) length: 127
Edge (8,20) length: 130
Edge (8,31) length: 115
Edge (9,8) length: 118
Edge (9,25) length: 209
Edge (10,3) length: 179
Edge (10,6) length: 106
Edge (10,7) length: 172
Edge (10,21) length: 167
Edge (10,22) length: 97
Edge (11,21) length: 138
Edge (11,24) length: 128
Edge (12,11) length: 133
Edge (12,22) length: 93
Edge (12,23) length: 164
Edge (13,12) length: 143
Edge (13,23) length: 207
Edge (14,2) length: 114
Edge (14,18) length: 147
Edge (14,28) length: 121
Edge (15,29) length: 128
Edge (15,30) length: 146
Edge (16,31) length: 112
Edge (17,14) length: 103
Edge (17,15) length: 109
Edge (17,29) length: 167
Edge (18,2) length: 116
Edge (18,17) length: 185
Edge (18,27) length: 145
Edge (19,17) length: 151
Edge (19,18) length: 301
Edge (20,21) length: 132
Edge (20,25) length: 134
Edge (21,24) length: 169
Edge (21,25) length: 129
Edge (22,11) length: 101
Edge (23,11) length: 108
Edge (23,24) length: 143
Edge (24,25) length: 243
Edge (26,4) length: 119
Edge (26,13) length: 139
Edge (27,1) length: 123
Edge (27,2) length: 160
Edge (28,6) length: 108
Edge (28,15) length: 78
Edge (28,17) length: 161
Edge (29,16) length: 155
Edge (29,19) length: 152
Edge (30,6) length: 152
Edge (30,7) length: 128
Edge (30,16) length: 77
Edge (30,29) length: 141
Edge (31,7) length: 79
Vertex 1 is not in tree
Vertex 2 is not in tree
Vertex 3 is not in tree
Vertex 4 is not in tree
Vertex 5 is not in tree
Vertex 6 is not in tree
Vertex 7 is not in tree
Vertex 8 is not in tree
Vertex 9 is not in tree
Vertex 10 is not in tree
Vertex 11 is not in tree
Vertex 12 is not in tree
Vertex 13 is not in tree
Vertex 14 is not in tree
Vertex 15 is not in tree
Vertex 16 is not in tree
Vertex 17 is not in tree
Vertex 18 is not in tree
Vertex 19 is not in tree
Vertex 20 is not in tree
Vertex 21 is not in tree
Vertex 22 is not in tree
Vertex 23 is not in tree
Vertex 24 is not in tree
Vertex 25 is not in tree
Vertex 26 is not in tree
Vertex 27 is not in tree
Vertex 28 is not in tree
Vertex 29 is not in tree
Vertex 30 is not in tree
Vertex 31 is not in tree