Introduction

A minimal-distance Hamiltonian path visits every vertex exactly once and minimizes the total edge cost. In JavaScript, the practical exact solution for small graphs is usually dynamic programming with bitmasks, not brute-force permutation generation.

This is still an exponential-time problem, so the goal is not to make it cheap for huge graphs. The goal is to solve small and medium instances correctly while avoiding obviously redundant work.

Path Versus Cycle

It helps to separate two related problems:

• a Hamiltonian path can start and end anywhere
• a Hamiltonian cycle must return to the starting vertex

If you are solving the path version, do not add the cost of returning to the first node. That one detail changes both the recurrence and the final answer.

Use Held-Karp Style Dynamic Programming

For a weighted graph stored as an adjacency matrix, a standard exact approach is:

• let dp[mask][last] mean the cheapest cost to visit the set of vertices in mask and finish at vertex last
• extend that partial path by trying every unvisited next vertex
• keep a parent table so the actual path can be reconstructed afterward

Here is a runnable JavaScript implementation:

1function minimalHamiltonianPath(dist) {
2  const n = dist.length;
3  const size = 1 << n;
4  const dp = Array.from({ length: size }, () => Array(n).fill(Infinity));
5  const parent = Array.from({ length: size }, () => Array(n).fill(-1));
6
7  for (let start = 0; start < n; start++) {
8    dp[1 << start][start] = 0;
9  }
10
11  for (let mask = 1; mask < size; mask++) {
12    for (let last = 0; last < n; last++) {
13      if ((mask & (1 << last)) === 0) continue;
14      const cost = dp[mask][last];
15      if (!Number.isFinite(cost)) continue;
16
17      for (let next = 0; next < n; next++) {
18        if (mask & (1 << next)) continue;
19        if (!Number.isFinite(dist[last][next])) continue;
20
21        const nextMask = mask | (1 << next);
22        const nextCost = cost + dist[last][next];
23
24        if (nextCost < dp[nextMask][next]) {
25          dp[nextMask][next] = nextCost;
26          parent[nextMask][next] = last;
27        }
28      }
29    }
30  }
31
32  const fullMask = size - 1;
33  let bestEnd = 0;
34  for (let v = 1; v < n; v++) {
35    if (dp[fullMask][v] < dp[fullMask][bestEnd]) {
36      bestEnd = v;
37    }
38  }
39
40  const path = [];
41  let mask = fullMask;
42  let current = bestEnd;
43
44  while (current !== -1) {
45    path.push(current);
46    const previous = parent[mask][current];
47    mask ^= 1 << current;
48    current = previous;
49  }
50
51  path.reverse();
52  return { distance: dp[fullMask][bestEnd], path };
53}
54
55const dist = [
56  [Infinity, 4, 2, 7],
57  [4, Infinity, 1, 3],
58  [2, 1, Infinity, 5],
59  [7, 3, 5, Infinity],
60];
61
62console.log(minimalHamiltonianPath(dist));

Why This Works Better Than Brute Force

Brute force checks every ordering of vertices, which grows like n!. The bitmask dynamic-programming approach still grows exponentially, but it reuses overlapping subproblems and runs in roughly O(n^2 * 2^n).

That is a major improvement for exact search. It is still only practical for relatively small n, but it is a real algorithmic step forward.

Represent Missing Edges Explicitly

If the graph is not complete, use Infinity for missing edges. The implementation above skips those transitions:

if (!Number.isFinite(dist[last][next])) continue;

That lets the same code work for both complete weighted graphs and sparse graphs represented as dense matrices.

When You Need a Heuristic Instead

If the graph has dozens or hundreds of vertices, exact Hamiltonian-path search is usually too expensive. At that point, use a heuristic or approximation strategy such as nearest neighbor, local search, or branch-and-bound with aggressive pruning.

Those methods do not guarantee the true optimum, but they can produce good answers in a realistic amount of time.

Common Pitfalls

• Solving the Hamiltonian cycle problem when the requirement is only a path.
• Forgetting to reconstruct the path after computing the minimum distance.
• Using 0 for missing edges instead of Infinity, which changes the cost model completely.
• Expecting an exact algorithm to scale to large graphs.
• Treating a greedy heuristic as if it guarantees the optimal path.

Summary

• A minimal Hamiltonian path visits every vertex once and minimizes total edge cost.
• In JavaScript, a Held-Karp style bitmask DP is a strong exact method for small graphs.
• Use dp[mask][last] to store the cheapest partial path ending at a specific vertex.
• Represent missing edges clearly and do not confuse a path with a cycle.
• For large graphs, switch from exact search to heuristics or approximations.