Please explain how in the TSP, "every subpath of a path of minimum distance is itself a minimum distance"?

Question

According to wikipedia, and many other sources I have read through, the Held-Karp algorithm is based on the idea that "every subpath of a path of minimum distance is itself a minimum distance."

I was hoping someone could explain this concept to me, because that claim doesn't seem true to me at all. If every subpath was a minimum distance, then that would mean that every pair of edges (3 connected cities) would itself be a minimum distance, which would mean that those are simply the two best edges connected to each other, which would also mean that a basic greedy algorithm would output an optimal TSP circuit every time.

So, clearly I am missing something conceptually. Help!

Answer 1

Every subpath in a path of minimum distance is a path of minimum distance between the endpoints of the subpath. For example if $a \to b \to c \to d \to e$ is a path of minimum distance from $a$ to $e$, then $b \to c \to d$ must be a path of minimum distance from $b$ to $d$. This is because if, say, $b \to c' \to d$ was a shorter path from $b$ to $d$, you could substitute this for $b \to c \to d$ in your original path, giving you $a \to b \to c' \to d \to e$ which is shorter than $a \to b \to c \to d \to e$.

This doesn't mean that a greedy algorithm works. In a greedy approach, starting from $a$, you might start with an edge of shortest distance $a \to z$. But maybe $z$ is farther from your goal than some of the other possible alternatives for the first step.