Index
Help
Created with Snap
Created with Snap
1
2
3
4
5
6
4x
.25x
.5x
1x
2x
4x
?
s = PickVertex()
dist[s] = 0
W.Insert(s,dist[s])
while
W.IsNotEmpty():
v = W.DeleteMin()
for
w
in
Neighborhood(v):
if
dist[w] == gInfinity:
pred[w] = v
dist[w] = dist[v] + length[(v,w)]
W.Insert(w,dist[w])
elif
dist[w] > dist[v] + length[(v,w)]:
pred[w] = v
dist[w] = dist[v] + length[(v,w)]
W.DecreaseKey(w,dist[w])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Edge (1,2) length: 1
Edge (2,3) length: 3
Edge (2,4) length: 1
Edge (3,5) length: -2
Edge (4,5) length: 1
Edge (5,6) length: 1
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