Question: If it starts at the asterisked node, what will the shortest-path tree look like after Dijkstra's algorithm adds the first five edges in the following graph? What is the final shortest-path tree?
10 18 12 1
o-----o-----*-----o-----o
| | | | _/
12| 2| 1| 2| _/13
| 16 | 16 | 14 |/
o-----o-----o-----o
| | | |
1| 16| 5| 20|
| | | |
o-----o-----o-----o
15 2 22
Answer: After five iterations we will have
o o *-----o-----o
|
|
|
o o o o
|
|
|
o o-----o o
After the algorithm is complete we will have
10 18 12 1
o-----o-----*-----o-----o
| |
1| 2|
16 | |
o o-----o o
| |
1| 5|
| |
o-----o-----o-----o
15 2 22