a shortest-path tree rooted at vertex v is a spanning tree T of G, such that the path distance from root v to any other vertex u in T is the shortest path distance from v to u in G.
Path |
s |
a |
b |
c |
d |
parent |
{ } |
0 |
∞ |
∞ |
∞ |
∞ |
- |
{ s } |
- |
2 |
7 |
∞ |
∞ |
s (parent of a) |
{ s,a } |
- |
- |
min(7,5) = 5 |
10 |
7 |
a (parent of b) |
{ s,a,b } |
- |
- |
- |
min(10,6) = 6 |
7 |
b (parent of c) |
{ s,a,b,c } |
- |
- |
- |
- |
min(7,8) = 7 |
a (parent of d) |
So the graph has edges sa, ab, bc and ad
so sum = sa+ab+bc+ad = 2+3+1+5 = 11