The Travelling Salesman Problem (Edexcel A-Level Further Mathematics): Flashcards

Shortest route visiting every vertex exactly once and returning to start

Complete graph

$\text{Wt}(A \to C) \leq \text{Wt}(A \to B) + \text{Wt}(B \to C)$

Infinity ($\infty$)

Upper bound

Start at the initial vertex

Move to nearest unvisited vertex

Simple and fast

May not give optimal solution

Use shortcuts with shorter connections