Algorithm: similar to shortest path.

Extra info for each entry in READY: length of shortest known path to this node from any node in the tree built so far. Note that the shortest path to the nearest node N is always a single edge.

1. Pick any node X as your starting point. Place <X,empty path,0> on READY.

2. Pick <N,P,L> on READY with minimum L.
   • Process it: record arc P -> N.

   • Remove it from READY, and mark it as PROCESSED.

   • Look up N's neighbours {N1, N2...Nk} connected to N by edges with weights W1,W2,...Wk. Ignore those that are PROCESSED.

     For each UNPROCESSED neighbour Ni:

     • Create triple <Ni,N,Wi>

     • Add triple to READY - if there is already a triple for Ni on READY, only add the new one (and delete the old one) if its path length (weight) is smaller.

3. Repeat step 2 until READY is empty.