1. A depth-first search. 2. From among the unallowed vertices, we select the vertex with the smallest current value in the distance array. This works because the current distance array contains the...

1. A depth-first search.

2. From among the unallowed vertices, we select the vertex with the smallest current value in the distance array. This works because the current distance array contains the correct distance values if we are permitting only allowed vertices, and the currently allowed vertices are the n-1 closest vertices. Therefore, the shortest path to the n^th
closest vertex must pass through only currently allowed vertices, and therefore the distance array contains the correct value for that n^th
closest vertex.