Implementation of Christofides Algorithm for TSP in python.
This package(Christofides) provides a way to implement Christofides algorithm for solving Travelling Saleman Problem(TSP) to obtain an approximate solution on an undirected graph(Distance Matrix) provided as an upper Triangular matrix. The Distance from a node on to itself is assumed 0.
Use the compute() function which takes as input a distance_matrix and returns a Christofides solution as follows:
from pyChristofides import christofides TSP = christofides.compute(distance_matrix)
The Distance Matrix is an upper Triangular matrix with distance from a node on to itself 0, since Christofides algorithm could only be applied for undirected graphs. Also the distance between a node on to itself is practically 0. Example for distance_matrix is as follows, distance_matrix =
[[0,45,65,15], [0,0,56,12], [0,0,0,89], [0,0,0,0]]
The above distance_matrix should be provided as an input to christofides.compute(), when we want to calculate TSP for distance =
[[0,45,65,15], [45,0,56,12], [65,56,0,89], [15,12,89,0]]
scipy, numpy, networkx, munkres