A Hamiltonian graph, also called a Hamilton graph, is a graph possessing a Hamiltonian cycle (or circuit).
Travelling salesman problem (or TSP)
Travelling salesman problem asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"
The problem belongs to the class of NP-complete problems.
There are two algorithms presented here:
- LatinComposition
- Branch and bound (BnB)
string input =
@"5
- 24 17 8 -
1 - 3 - 11
17 8 - - 6
8 - 9 - 12
17 11 6 - -
";
int?[,] weights = GraphUtil.FromMatrixFormat(input);
int[] cycle = new BranchAndBound(weights).GetShortestHamiltonianCycle();
// output: "0 -> 3 -> 4 -> 2 -> 1 -> 0"
Console.WriteLine(string.Join(" -> ", cycle));
// or: "A -> D -> E -> C -> B -> A"
string cycleSymbols = string.Join(" -> ", cycle.Select(vertex => (char)(vertex + 'A')));
Console.WriteLine(cycleSymbols);