Function tsp_held_karp 

pub fn tsp_held_karp(dist: &[Vec<f64>]) -> Option<(f64, Vec<usize>)>

Solves the Travelling Salesman Problem exactly using the Held-Karp bitmask dynamic programming algorithm.

Given a complete weighted directed graph represented as a distance matrix, finds the minimum-cost Hamiltonian circuit starting and ending at node 0.

Algorithm

Let dp[mask][v] be the minimum cost to reach node v having visited exactly the nodes encoded in mask (bit i set ⟹ node i visited), starting from node 0.

Recurrence:
dp[mask | (1 << u)][u] = min(dp[mask][v] + dist[v][u])
for all v in mask and u not in mask.

Answer:
min over v of (dp[all_visited][v] + dist[v][0])

Arguments

• dist — n × n distance matrix. dist[i][j] is the cost of going from node i to node j. Use f64::INFINITY for missing edges.

Returns

Some((cost, path)) — the minimum tour cost and the node visit order (starts and ends at node 0).
None — no Hamiltonian circuit exists (some required edge is INFINITY), or dist is empty.

Complexity

O(2^n · n²) time, O(2^n · n) space. Practical for n ≤ 20.

Panics

Panics if dist is not square (all rows must have the same length as the number of rows).

Examples

use graph_advanced::tsp_held_karp;

// 4-node complete graph with known optimal tour cost 35.
//        0   1   2   3
let dist = vec![
    vec![0.0, 10.0, 15.0, 20.0], // from 0
    vec![10.0, 0.0, 35.0, 25.0], // from 1
    vec![15.0, 35.0, 0.0, 30.0], // from 2
    vec![20.0, 25.0, 30.0, 0.0], // from 3
];

let (cost, path) = tsp_held_karp(&dist).unwrap();
assert_eq!(cost, 80.0); // 0→1(10)+1→3(25)+3→2(30)+2→0(15)
assert_eq!(path.first(), Some(&0));
assert_eq!(path.last(), Some(&0));
assert_eq!(path.len(), 5); // 4 nodes + return to 0