Consider a day in a salesman's life. He wants to visit a number of cities in a day. Each city is separated by a distance and he wants to visit each city and return to the origin city with the minimum traveling distance possible. This problem of finding the shortest possible route is termed as "Traveling Salesman Problem (TSP)".
TSP problem can be defined in the graph terms as each city being represented as a node and the edge connecting the two nodes representing the distance between them. The solution is a shortest possible path in the graph which traverses through each node and reach the origin node with the minimum possible weight.
Traveling salesman problem is an NP-hard problem.
Christofides algorithm is an approximate algorithm for solving Traveling Salesman Problem (TSP) in a metric space. It was first published by Nicos Christofides in 1976. It guarantees that its solutions will be within a factor of 1.5 of the optimal solution length.
By metric space we mean that the distance function satisfies the following properties:
-
Positive:
$D(x,y)>=0$ -
Symmetry:
$D(x,y) = D(y,x)$ -
Reflexive:
$D(x,y) = 0$ iff$x=y$ -
Triangle Inequaltiy:
$D(x,z) + D(z,y) >= D(x,y)$
The algorithm consists of the following steps:
- Minimum Spanning Tree
- Odd Degree Vertices
- Minimum Weight Perfect Matching
- Connected Multigraph
- Eulerian Circuit
- Hamiltonian Circuit
More details about the algorithm can be found on the wikipedia page.
Christofides algorithm is O(n3) because this is the time it takes to calculate minimum weight perfect matching.
python main.py
To change the parameters of the code, open main.py. Different parameters available are:
txt_file : Input graph file
debug : Whether to save intermediate outputs as well
source_node : Source Node
debug_folder : Debug folder where intermediate outputs will be saved