Skip to content

Solves Travelling salesman problem with searching for Hamiltonian Circuit

License

Notifications You must be signed in to change notification settings

sagidM/HamiltonianGraph

Repository files navigation

Hamiltonian Graph

NuGet Build Status Build status

What is that?

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.

Project

There are two algorithms presented here:

Usage

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);

About

Solves Travelling salesman problem with searching for Hamiltonian Circuit

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published