V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Traveling Salesperson DP

Use a bitmask for visited cities and end-position states to assemble the shortest Hamiltonian tour.

Core idea

State dp[mask][i] stores the shortest path that starts at city zero, visits exactly the mask, and ends at i. Remove i to enumerate the predecessor of the final edge.

Read the visualization

Rows decode visited-city bitmasks and columns choose the endpoint. Each filled cell highlights predecessor states, and the closing phase adds one edge back to the start.

0123
00010
0011
0101
0111
1001
1011
1101
1111

Start at city zero with only its bit set and zero path cost.

1function tsp(d: number[][]): number {
2 const n = d.length, FULL = (1 << n) - 1;
3 const dp = Array.from({ length: 1 << n }, () => new Array(n).fill(Infinity));
4 dp[1][0] = 0; // from init 0 init
5 for (let mask = 3; mask <= FULL; mask++) {
6 if (!(mask & 1)) continue; // init start point
7 for (let i = 1; i < n; i++) {
8 if (!(mask & (1 << i))) continue;
9 const prev = mask ^ (1 << i); // fill i fill set
10 for (let j = 0; j < n; j++) // up one fill j
11 if (prev & (1 << j))
12 dp[mask][i] = Math.min(dp[mask][i], dp[prev][j] + d[j][i]);
13 }
14 }
15 let best = Infinity;
16 for (let i = 1; i < n; i++) // return to start point close tail
17 best = Math.min(best, dp[FULL][i] + d[i][0]);
18 return best;
19}
distance4 symmetric cities matrix ( see code)
state number2ⁿ·n = 64
1 / 15

Complexity and tradeoffs

Time: O(n^2 2^n). Space: O(n 2^n). Held-Karp is exponential but far smaller than checking all n! tours.

Invariant: Every finite state visits each city in its mask exactly once and ends at the column city.

Where it fits

Held-Karp is practical only for small city counts, but its bitmask-state technique is central to subset scheduling, assignment, and visit-all-nodes problems.