Idea

We will list out all the nodes of G in order of their distance from s. This will insure that we won't miss any short cuts as we go.

• Consider shortest edge out of s (to v). No other path to v can be shorter. Why? Moreover, v is a closest node to s. Why?

• Therefore, we can include (s,v) in the shortest-path tree.
• Mark v with its distance from s, w((s,v)), and now look for the next closest node. Which will it be?
• Basically, keep a set of ``inside'' and ``outside'' nodes and move the outside nodes inside one at a time in order of their distance.