Travelling Salesman Problem (TSP) using Dynamic Programming

Today we are discussing the Travelling Salesman Problem (TSP) and the Dynamic Programming
(DP) Bellman–Held–Karp formulation (बेलमैन-हेल्ड-कार्प एल्गोरिथम).

What is TSP?
The Travelling Salesman Problem (TSP) asks:
Find the shortest route that visits every city exactly once and returns to the starting city.

DP State Definition

Where:
 i = current city
 S = set of unvisited cities
 w(i, j) = cost from city i to city j
 g(i, S) = minimum cost to complete tour starting at i, visiting all in S, then returning to
start
Base Case
When S is empty:

This means → return to starting city A.

Example:-
Distance Matrix Used

A B C D
A 0 16 11 6
B 8 0 13 16
C 4 7 0 9
D 5 12 2 0
#include <bits/stdc++.h>
using namespace std;

// We will use a very large value to represent infinity

const int INF = 1e9;

int main() {

// ---------------------------------------------------------------
// 1. DISTANCE MATRIX (Taken exactly from your image)
// ---------------------------------------------------------------
// A B C D
// A 0 16 11 6
// B 8 0 13 16
// C 4 7 0 9
// D 5 12 2 0
//
// dist[i][j] represents the cost of travelling from city i to city j.
// City Index: 0=A, 1=B, 2=C, 3=D
// ---------------------------------------------------------------
vector<vector<int>> dist = {
{0, 16, 11, 6},
{8, 0, 13, 16},
{4, 7, 0, 9},
{5, 12, 2, 0}
};

int n = 4; // Number of cities (A, B, C, D)

int N = 1 << n; // Total subsets = 2^n (Here 2^4 = 16)

// dp[mask][i] = minimum cost to reach city i using the subset "mask"

vector<vector<int>> dp(N, vector<int>(n, INF));

// parent[mask][i] stores the previous city before reaching city i

// This is used later for reconstructing the final optimal path.
vector<vector<int>> parent(N, vector<int>(n, -1));

// ---------------------------------------------------------------
// 2. STARTING POINT
// ---------------------------------------------------------------
// We start from city A (index 0)
// mask = 0001 means only city A is visited.
dp[1][0] = 0;

// ---------------------------------------------------------------
// 3. HELD-KARP DP TRANSITION
// ---------------------------------------------------------------
// For each subset of cities (mask)
for (int mask = 1; mask < N; mask++) {

// Try to end at city 'u'

for (int u = 0; u < n; u++) {

// Check if city 'u' is included in this subset

if (mask & (1 << u)) {

// Next city 'v' which is not yet visited

for (int v = 0; v < n; v++) {

if (!(mask & (1 << v))) { // city v not in mask

int newMask = mask | (1 << v); // include v

int newCost = dp[mask][u] + dist[u][v];

// Update if we found a cheaper route

if (newCost < dp[newMask][v]) {
dp[newMask][v] = newCost;
parent[newMask][v] = u; // store the last city
}
}
}
}
}
}

// ---------------------------------------------------------------
// 4. COMPLETE THE TOUR (RETURN TO START A)
// ---------------------------------------------------------------
int finalMask = N - 1; // 1111 → all cities visited
int bestCost = INF;
int lastCity = -1;

// Try ending at any city except A, and return to A

for (int i = 1; i < n; i++) {
int cost = dp[finalMask][i] + dist[i][0]; // return to A
if (cost < bestCost) {
bestCost = cost;
lastCity = i;
}
}

// ---------------------------------------------------------------
 // 5. PATH RECONSTRUCTION
// ---------------------------------------------------------------
vector<int> path;
int mask = finalMask;
int curr = lastCity;

// Backtrack using the parent table

while (curr != -1) {
path.push_back(curr);
int prev = parent[mask][curr];
mask ^= (1 << curr); // Remove current city from mask
curr = prev; // Move to previous city
}

// Finally add starting city A

path.push_back(0);
reverse(path.begin(), path.end());

// ---------------------------------------------------------------
// 6. OUTPUT
// ---------------------------------------------------------------
cout << "Minimum Travelling Salesman Cost = " << bestCost << endl;

cout << "Optimal Path: ";

for (int i = 0; i < path.size(); i++) {
cout << char('A' + path[i]);
if (i < path.size() - 1) cout << " -> ";
}
cout << endl;

return 0;
}