Shortest Hamiltonian Cycle — Problem Statement & Solution Guide
Problem Description
Given an undirected graph with n vertices, where each vertex represents a town and the edges represent roads with varying distances, find the shortest possible route that visits each vertex exactly once and returns to the starting vertex. The graph is represented as an adjacency matrix, where the weight of each edge corresponds to the distance between two towns.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Shortest Hamiltonian Cycle"
WHY DOES IT MATTER?
The bitmask DP pattern captures exponential‑state problems where the solution depends on a subset of items and a last element, a recurring theme in routing, scheduling, and subset‑sum variants. Mastering it lets engineers solve many NP‑hard exact problems within feasible limits.
OPTIMIZATION CHALLENGE
The breakthrough is recognizing that the sub‑problem state can be compressed into a bitmask plus a terminal vertex, turning an O(n!) search into O(n^2·2^n) by reusing overlapping sub‑tours.
REAL-WORLD CONNECTION
Think of a distributed microservice orchestrator that must visit a set of data shards exactly once to perform a batch update and then return to the coordinator. The orchestrator must decide the order of shard visits to minimize total network latency, mirroring the Hamiltonian cycle computation.
When coding the DP, pre‑compute all pairwise distances, use an integer mask (int for n≤31, long long for n≤63), and iterate masks in increasing order; also, store DP in a 2‑D array of size (1<<n) × n to avoid hashmap overhead.
COMPLEXITY AT A GLANCE
O(n^2 * 2^n)O(n * 2^n)Core Theory — Why This Approach?
The Shortest Hamiltonian Cycle problem is a classic formulation of the Traveling Salesman Problem (TSP) on an undirected weighted graph. The goal is to find a minimum‑weight permutation of the vertices that starts and ends at the same vertex while visiting every other vertex exactly once. A naïve enumeration of all n! permutations quickly becomes infeasible because the factorial growth outpaces any realistic time budget even for moderate n (e.g., n=20 yields ~2.4×10^18 possibilities). This exponential blow‑up forces us to look for combinatorial structures that allow overlapping sub‑problems to be reused.
Dynamic programming with bitmasking, often called the Held‑Karp algorithm, exploits the fact that the optimal tour to a set of visited vertices ending at a particular vertex depends only on the subset of visited vertices and the last vertex, not on the order in which the subset was traversed. By representing subsets as bit masks and storing the best cost for each (mask, last) pair, we can build solutions for larger subsets from smaller ones. The recurrence DP[mask][i] = min_{j in mask, j≠i} (DP[mask \ {i}][j] + dist[j][i]) captures this principle, leading to a time complexity of O(n^2·2^n) and space O(n·2^n), which is the best known exact solution for general graphs.
The optimal paradigm therefore shifts from brute‑force permutation generation to state‑space reduction via DP and bit manipulation. This approach is tractable for n up to ~20‑22 on modern hardware, making it the go‑to method for interview problems that ask for the exact shortest Hamiltonian cycle on an adjacency matrix.
Interview Questions on This Problem
Q1How would you solve the Shortest Hamiltonian Cycle problem for n ≤ 20 and why is the Held‑Karp DP algorithm preferred over backtracking?
I would use DP with bitmasking (Held‑Karp). It stores the optimal cost to reach each subset of vertices ending at a specific vertex, allowing us to reuse sub‑solutions. This reduces the time from O(n!) to O(n^2·2^n) and fits comfortably for n ≤ 20, whereas pure backtracking still explores factorial possibilities.
Q2In a fintech platform, you need to compute the cheapest route for a set of currency conversion nodes (edges weighted by spread). Which graph property lets you apply the same DP technique, and how would you handle asymmetric spreads?
The graph remains a complete weighted directed graph because conversion spreads can differ per direction. The DP recurrence works unchanged for directed graphs; we just use the directed weight matrix. The key property is that the cost of extending a partial tour depends only on the last node and the set of visited nodes, enabling the same bitmask DP.
Q3A high‑growth startup wants to approximate the TSP for up to 10,000 cities in real time. What heuristic would you suggest and why is it acceptable compared to the exact DP solution?
I would suggest a nearest‑neighbor or Christofides heuristic (if the graph satisfies triangle inequality). These run in O(n^2) or O(n^3) and produce tours within a known factor of the optimum, which is acceptable when exact DP is impossible due to exponential time and memory constraints for n=10,000.
Examples
Input
[[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
Output
80
Explanation: Step-by-step: with input [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]], we start at vertex 0, then visit vertex 1 (distance 10), then vertex 3 (distance 25), then vertex 2 (distance 30), and finally return to vertex 0 (distance 15), giving a total distance of 10 + 25 + 30 + 15 = 80.
Input
[[0, 5, 10], [5, 0, 3], [10, 3, 0]]
Output
18
Explanation: Step-by-step: with input [[0, 5, 10], [5, 0, 3], [10, 3, 0]], we start at vertex 0, then visit vertex 2 (distance 10), then vertex 1 (distance 3), and finally return to vertex 0 (distance 5), giving a total distance of 10 + 3 + 5 = 18.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Optimal Approach & Strategy
Use Held‑Karp DP with bitmasking: DP[mask][i] stores the cheapest path that visits exactly the vertices in mask and ends at i, built from smaller masks.
Brute Force Approach
Generate all n! permutations of vertices, compute the tour length for each, and keep the minimum.
Verified Code Solutions
function solution(graph) {
const n = graph.length;
let minDistance = Infinity;
const visited = new Array(n).fill(false);
visited[0] = true;
function dfs(currentVertex, currentDistance, visited) {
if (currentDistance > minDistance) return;
if (visited.every(v => v)) {
minDistance = Math.min(minDistance, currentDistance + graph[currentVertex][0]);
return;
}
for (let i = 0; i < n; i++) {
if (!visited[i] && graph[currentVertex][i] !== 0) {
visited[i] = true;
dfs(i, currentDistance + graph[currentVertex][i], visited);
visited[i] = false;
}
}
}
dfs(0, 0, visited);
return minDistance;
}class Solution {
public:
int solution(vector<vector<int>>& graph) {
int n = graph.size();
int minDistance = INT_MAX;
vector<bool> visited(n, false);
visited[0] = true;
dfs(graph, 0, 0, visited, minDistance);
return minDistance;
}
void dfs(vector<vector<int>>& graph, int currentVertex, int currentDistance, vector<bool>& visited, int& minDistance) {
if (currentDistance > minDistance) return;
if (isAllVisited(visited)) {
minDistance = min(minDistance, currentDistance + graph[currentVertex][0]);
return;
}
for (int i = 0; i < graph.size(); i++) {
if (!visited[i] && graph[currentVertex][i] != 0) {
visited[i] = true;
dfs(graph, i, currentDistance + graph[currentVertex][i], visited, minDistance);
visited[i] = false;
}
}
}
bool isAllVisited(vector<bool>& visited) {
for (bool b : visited) {
if (!b) return false;
}
return true;
}
};class Solution {
public int solution(int[][] graph) {
int n = graph.length;
int[] minDistance = new int[] {Integer.MAX_VALUE};
boolean[] visited = new boolean[n];
visited[0] = true;
dfs(graph, 0, 0, visited, minDistance);
return minDistance[0];
}
private void dfs(int[][] graph, int currentVertex, int currentDistance, boolean[] visited, int[] minDistance) {
if (currentDistance > minDistance[0]) return;
if (isAllVisited(visited)) {
minDistance[0] = Math.min(minDistance[0], currentDistance + graph[currentVertex][0]);
return;
}
for (int i = 0; i < graph.length; i++) {
if (!visited[i] && graph[currentVertex][i] != 0) {
visited[i] = true;
dfs(graph, i, currentDistance + graph[currentVertex][i], visited, minDistance);
visited[i] = false;
}
}
}
private boolean isAllVisited(boolean[] visited) {
for (boolean b : visited) {
if (!b) return false;
}
return true;
}
}def solution(graph):
n = len(graph)
min_distance = float('inf')
visited = [False] * n
visited[0] = True
def dfs(current_vertex, current_distance, visited):
nonlocal min_distance
if current_distance > min_distance:
return
if all(visited):
min_distance = min(min_distance, current_distance + graph[current_vertex][0])
return
for i in range(n):
if not visited[i] and graph[current_vertex][i] != 0:
visited[i] = True
dfs(i, current_distance + graph[current_vertex][i], visited)
visited[i] = False
dfs(0, 0, visited)
return min_distancefunction solution(graph) {
const n = graph.length;
let minDistance = Infinity;
const visited = new Array(n).fill(false);
visited[0] = true;
function dfs(currentVertex, currentDistance, visited) {
if (currentDistance > minDistance) return;
if (visited.every(v => v)) {
minDistance = Math.min(minDistance, currentDistance + graph[currentVertex][0]);
return;
}
for (let i = 0; i < n; i++) {
if (!visited[i] && graph[currentVertex][i] !== 0) {
visited[i] = true;
dfs(i, currentDistance + graph[currentVertex][i], visited);
visited[i] = false;
}
}
}
dfs(0, 0, visited);
return minDistance;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.