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
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,7) length: 150.00
Edge (2,1) length: 158.11
Edge (2,6) length: 150.00
Edge (3,2) length: 200.00
Edge (3,5) length: 206.16
Edge (4,3) length: 212.13
Edge (4,13) length: 250.00
Edge (5,4) length: 206.16
Edge (6,1) length: 180.28
Edge (6,11) length: 150.00
Edge (7,8) length: 141.42
Edge (7,6) length: 158.11
Edge (8,9) length: 158.11
Edge (9,17) length: 158.11
Edge (10,9) length: 150.00
Edge (10,16) length: 206.16
Edge (11,8) length: 250.00
Edge (11,5) length: 180.28
Edge (11,10) length: 158.11
Edge (12,5) length: 150.00
Edge (12,11) length: 158.11
Edge (13,12) length: 206.16
Edge (14,13) length: 200.00
Edge (15,14) length: 206.16
Edge (16,15) length: 150.00
Edge (17,16) length: 158.11
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