How can we keep track of which nodes are the closest?
- Keep an array d to hold distances: d[v] is the best known
distance to node v.
- When a node is added to the tree, see if any new shortcuts have
been discovered, thus shortening the best known distance to some node
v.
- What data structure ought to hold this kind of information?
Next: Initialization and Improvement
Up: DIJKSTRA'S ALGORITHM
Previous: Idea