Offensive Security Researcher & Quantum Cryptography Analyst

Salesperson Routing Algorithm: Working, Explanation, and Route Planning

Abdul Wahab Junaid
Salesperson Routing algorithm and working of this algorithm

Salesperson Routing algorithm and working of this algorithm

I want to describe this as one of the most famous problems I’ve encountered in all of computer science and operations research: given a list of cities and the distances between each pair of them, find the shortest possible route that visits every city exactly once and returns to the starting point. This is the Traveling Salesperson Problem (TSP), and I find it fascinating precisely because it’s so easy to state yet computationally so hard to solve exactly for large inputs — it’s a canonical NP-hard problem that has driven decades of algorithmic research.

History and Background

The mathematical roots of the problem trace back to the 1800s, with William Rowan Hamilton’s icosian game (1857) touching on the idea of visiting every vertex of a graph exactly once. The problem in its modern “traveling salesman” framing was studied more formally starting in the 1930s, notably by Karl Menger in Vienna. It gained major research traction in the 1950s and 1960s, when Dantzig, Fulkerson, and Johnson (1954) solved a 49-city instance using linear programming and cutting planes — a landmark achievement that essentially founded the field of combinatorial optimization. The problem was later shown to be NP-hard, cementing its central role in complexity theory.

Problem Statement

I define it as: given a complete weighted graph $G = (V, E)$ where $V$ represents cities and edge weights represent distances (or travel costs) between them, find a Hamiltonian cycle (a cycle visiting every vertex exactly once and returning to the start) with the minimum possible total edge weight.

Core Concepts

How It Works

I’ll describe the Held–Karp dynamic programming approach, which is the standard exact method:

  1. I fix a starting city, say city 0.
  2. I define a state $(S, j)$ representing the minimum cost of a path that starts at city 0, visits exactly the set of cities $S$ (which includes $j$), and ends at city $j$.
  3. Base case: $C({0}, 0) = 0$.
  4. For each subset $S$ containing city 0 and each city $j \in S$ (other than 0), I compute $C(S, j)$ by considering every possible previous city $k \in S \setminus {j}$: $C(S, j) = \min_{k}\big(C(S \setminus {j}, k) + d(k, j)\big)$.
  5. I build up these values for increasing subset sizes, from small subsets to the full set of all cities.
  6. The final answer is $\min_j \big(C(V, j) + d(j, 0)\big)$ — the minimum cost of a path visiting all cities, closed back to the start.

Working Principle

The logic here is dynamic programming over subsets, exploiting the principle of optimality: the best way to visit a specific set of cities and end at a particular city can be built from the best way to visit a slightly smaller set and end at some other city, plus one more edge. By using a bitmask to represent which cities have been visited, I can systematically enumerate all $2^n$ subsets without redundant recomputation, which is what brings the complexity down from factorial ($n!$, brute-force permutations) to exponential-but-much-smaller ($n^2 2^n$).

Mathematical Foundation

The Held–Karp recurrence is:

$$ C(S, j) = \min_{k \in S \setminus {j}} \big[ C(S \setminus {j}, k) + d(k,j) \big] $$

with base case:

$$ C({1}, 1) = 0 $$

(using city 1 as the fixed start, 0-indexed or 1-indexed depending on convention), and final answer:

$$ \text{Optimal Tour Cost} = \min_{j \neq 1} \big[ C(V, j) + d(j,1) \big] $$

For heuristic methods, the 2-opt local search improvement swaps two edges whenever:

$$ d(a,b) + d(c,d) > d(a,c) + d(b,d) $$

for edges $(a,b)$ and $(c,d)$ in the current tour, replacing them to strictly reduce total tour length.

Diagrams

flowchart TD
    Start([Start: n cities, distance matrix]) --> Base["C({start}, start) = 0"]
    Base --> Loop["For each subset size, for each subset S containing start"]
    Loop --> Inner["For each city j in S: compute C(S,j) via min over previous city k"]
    Inner --> Grow{All subset sizes processed?}
    Grow -- No --> Loop
    Grow -- Yes --> Close["Compute min over j of C(V,j) + d(j,start)"]
    Close --> End([Return optimal tour cost and path])

Pseudocode

function HeldKarp(dist[1..n][1..n]):
    // dp[S][j] = min cost path visiting set S, ending at city j, starting at city 1
    dp[{1}][1] = 0

    for subsetSize from 2 to n:
        for each subset S of {1,...,n} containing city 1, with |S| = subsetSize:
            for each j in S, j != 1:
                dp[S][j] = infinity
                for each k in S, k != j:
                    candidate = dp[S - {j}][k] + dist[k][j]
                    if candidate < dp[S][j]:
                        dp[S][j] = candidate

    fullSet = {1, ..., n}
    best = infinity
    for j from 2 to n:
        candidate = dp[fullSet][j] + dist[j][1]
        if candidate < best:
            best = candidate

    return best

Step-by-Step Example

I’ll use a small 4-city example (A, B, C, D) with distances: A-B=10, A-C=35, A-D=25, B-C=15, B-D=30, C-D=20, starting from A.

For 4 cities, the Held–Karp table has states for subsets of {B,C,D} paired with an ending city. Rather than enumerating the full table, I’ll trace the resulting optimal tour directly, since with only 4 cities I can also reason via the 3 distinct Hamiltonian cycles (accounting for direction and reflection symmetry):

The minimum is A→B→C→D→A with total cost 70. Held–Karp’s dynamic programming table, built up subset by subset, arrives at this same value of 70 as the optimal tour cost.

Time Complexity

Space Complexity

Held–Karp requires $O(n \cdot 2^n)$ space to store the DP table indexed by subset and ending city, which is the main practical bottleneck limiting it to smaller instances even though its time complexity alone might seem tractable for slightly larger $n$. Heuristic methods like nearest neighbor or 2-opt require only $O(n^2)$ space for the distance matrix and $O(n)$ for the current tour.

Correctness Analysis

Held–Karp’s correctness follows directly from the principle of optimality applied over subsets: $C(S, j)$ represents the true minimum cost of visiting exactly the cities in $S$ ending at $j$, and by induction on subset size, this is correctly built from smaller, already-optimal subset solutions — because any optimal path visiting $S$ and ending at $j$ must have arrived from some specific previous city $k \in S \setminus {j}$, and the sub-path up to $k$ must itself be optimal for the set $S \setminus {j}$ (otherwise I could substitute in a cheaper sub-path and improve the whole tour, a contradiction). Since I enumerate all valid predecessors $k$, the recurrence is guaranteed to find the true minimum. Heuristic methods like 2-opt, by contrast, only guarantee convergence to a local optimum, not global optimality — correctness there is about monotonic improvement, not about reaching the true minimum.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>
#include <limits.h>

#define N 4  // number of cities
#define INF INT_MAX

int dist[N][N] = {
    {0, 10, 35, 25},
    {10, 0, 15, 30},
    {35, 15, 0, 20},
    {25, 30, 20, 0}
};

int dp[1 << N][N];  // dp[subset][j]

int heldKarp() {
    for (int i = 0; i < (1 << N); i++)
        for (int j = 0; j < N; j++)
            dp[i][j] = INF;

    dp[1][0] = 0;  // start at city 0, subset {0}

    for (int subset = 1; subset < (1 << N); subset++) {
        if (!(subset & 1)) continue;  // must include city 0
        for (int j = 0; j < N; j++) {
            if (!(subset & (1 << j)) || dp[subset][j] == INF) continue;
            for (int k = 0; k < N; k++) {
                if (subset & (1 << k)) continue;  // k already visited
                int nextSubset = subset | (1 << k);
                int newCost = dp[subset][j] + dist[j][k];
                if (newCost < dp[nextSubset][k])
                    dp[nextSubset][k] = newCost;
            }
        }
    }

    int fullSet = (1 << N) - 1;
    int best = INF;
    for (int j = 1; j < N; j++) {
        if (dp[fullSet][j] != INF) {
            int total = dp[fullSet][j] + dist[j][0];
            if (total < best) best = total;
        }
    }
    return best;
}

int main() {
    int result = heldKarp();
    printf("Optimal TSP tour cost: %d\n", result);
    return 0;
}

Sample Input and Output

Input: 4-city distance matrix as defined above (A=0, B=1, C=2, D=3).

Output:

Optimal TSP tour cost: 70

This matches my manual enumeration of A→B→C→D→A as the optimal tour.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version