The Travelling Salesman Problem

• The problem itself: find the tour of least weight that visits every vertex and returns to the start — classical (visit each exactly once) vs practical (visit each at least once).
• Table of least distances: turns a messy, incomplete "practical" network into a complete "classical" one, using the triangle inequality.
• Upper bound: built from a minimum spanning tree, doubled, then improved with a "shortcut."
• Lower bound: built with the "deleted vertex method" — remove a vertex, find the residual minimum spanning tree, add back the two cheapest connections.
• Nearest neighbour algorithm: a quick greedy method that also gives an upper bound (a real route you can walk).
• Solving completely: for small graphs, list every possible Hamiltonian cycle and find the cheapest — or show a found route matches the lower bound, proving it's optimal.

Picture a delivery driver who has to visit six villages and get back to their depot, doing the least total driving possible. That's the whole problem in one sentence: find the tour of least weight in a network.

A tour is a walk that starts at one vertex, visits every other vertex, and returns to where it started. There are two flavours of this problem, and the difference is subtle but important:

Here's the key trick that ties them together: if you build a table of least distances for a practical network, you effectively turn it into a classical problem — because now every vertex has a direct "shortest path" connection to every other vertex, even if that path passes through other villages.