teeline · algorithms/bhk
Bellman-Held-Karp — exact dynamic programming
BHK fills a table of subset costs: dp[mask][i] is the cheapest path from city 0 that visits exactly the cities in mask and ends at city i. Every cell is built from one smaller subset plus one edge — then the optimal route is read back through the recorded predecessors.
DP table — rows end city, columns subset
| end \ subset | 00001 | 00010 | 00011 | 00100 | 00101 | 00110 | 00111 | 01000 | 01001 | 01010 | 01011 | 01100 | 01101 | 01110 | 01111 | 10000 | 10001 | 10010 | 10011 | 10100 | 10101 | 10110 | 10111 | 11000 | 11001 | 11010 | 11011 | 11100 | 11101 | 11110 | 11111 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 180 | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · |
| 2 | · | 255 | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · |
| 3 | · | · | · | 180 | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · |
| 4 | · | · | · | · | · | · | · | 90 | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · |
| 5 | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | 201 | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · |
Subset on the map
Cell info
click a cell to see how its value was computed
Optimal
— (after the table fills)
Stats
subset size
2
bits set
00011
phase
forward
step
0
Mode
base cell filled next cell optimal route
Bellman-Held-Karp — the DP table fills subset by subset
Speed
Scenarios