Traveling Salesman Problem

External

• https://www.coursera.org/learn/algorithms-npcomplete/lecture/49MkW/the-traveling-salesman-problem
• https://www.coursera.org/learn/algorithms-npcomplete/lecture/uVABz/a-dynamic-programming-algorithm-for-tsp

Internal

• NP Completeness
• Dynamic Programming
• Bellman-Ford Shortest-Path Algorithm

Overview

The input is a complete undirected graph with non-negative edge costs. The output is a minimum cost tour (permutation of the vertices, a cycle that visits every vertex exactly once that minimize the sum of the edges). The brute force search running time is O(n!). The dynamic programming approach described here has a running time of O(n²2ⁿ).