algorithms_edu/problems/graph/
tsp.rs

1pub mod brute_force;
2pub mod dp;
3
4#[cfg(test)]
5mod tests {
6    use super::*;
7
8    use crate::algo::graph::WeightedAdjacencyMatrix;
9    #[test]
10    fn test_tsp() {
11        let mut dist = vec![vec![100.; 5]; 5];
12        // Assume matrix is symmetric for simplicity.
13        dist[1][3] = 1.;
14        dist[3][1] = 1.;
15
16        dist[3][0] = 2.;
17        dist[0][3] = 2.;
18
19        dist[0][2] = 3.;
20        dist[2][0] = 3.;
21
22        dist[2][4] = 4.;
23        dist[4][2] = 4.;
24
25        dist[4][1] = 5.;
26        dist[1][4] = 5.;
27        let dist: WeightedAdjacencyMatrix = dist.into();
28
29        let (best_dist, tour) = dp::TspSolver::solve(&dist, 1);
30        assert_eq!(best_dist, 15.);
31        assert_eq!(&tour, &[1, 3, 0, 2, 4]);
32
33        let (best_dist, tour) = brute_force::tsp(&dist, 1);
34        assert_eq!(best_dist, 15.);
35        assert_eq!(&tour, &[1, 3, 0, 2, 4]);
36    }
37}