Shortest Hamiltonian Path
HardGraphDynamic ProgrammingBitmaskMatrix
Description
Given an n x n weight matrix of a complete undirected graph (matrix[i][j] is the edge weight between i and j; matrix[i][i] = 0), return the minimum total weight of a Hamiltonian path (visiting every vertex exactly once). The path may start and end at any vertices.
Examples
Input:
matrix = [[0,1,2],[1,0,4],[2,4,0]]Output:
3Explanation:
Path 1-0-2 visits every vertex once with total weight 1+2 = 3.
Input:
matrix = [[0]]Output:
0Explanation:
A graph with a single vertex has trivial Hamiltonian path length of 0.
Input:
matrix = [[0,10],[10,0]]Output:
10Explanation:
With only two vertices the path uses the single edge of weight 10.
Constraints
- •
1 ≤ n ≤ 12 - •
0 ≤ matrix[i][j] ≤ 10⁴