Shortest Path

Now, the problem has become one of doing a single-source shortest path search, which terminates when a complete tour is reached.

We can't actually construct the entire graph, but we can generate it on an as-needed basis.

Dijkstra's algorithm will only visit as many partial tours as have weight less than or equal to $\mbox{\rm OPT}$. But, that's still pretty inefficient.