An implementation of three different TSP approximation algorithms
Github Repository
Nearest Neighbor Algorithm
The path is decided by which point is closest to the current point. Runs in O(n2) time, doesn't find most efficient path.
Nearest-Neighbor(P)
Stack path
boolean array V of size ||P|| populated with false path.push(1) i = 0 while(||path|| < ||P||) Vi = true closest = closest point to Pi path.push(closest) i = closest path.push(1)
return path
2-approx Algorithm
Construct path by creating an MST (Prim's was used in this example) then performing depth-first search. O(n2)
Two-Approximate(P)
Stack path
generate complete weighted graph of P MST = minimum spanning tree of weighted graph
adjacency matrix A of size ||P|| populated with 0 for(i in MST)
add i to adjacency matrix
run depth-first-search on adj and add each visited node to path path.push(1)
return path
1.5-approx Algorithm (Christofides)
Construct path by creating an MST, find a minimum-cost perfect matching for odd-degree vertices, add edges and form an Eulerian circuit, and then remove all repeated vertices. O(n3)
Christofides(P)
generate complete weighted graph of P MST = minimum spanning tree of weighted graph odd = all the odd degree vertices MST match = minimum weight matching E = Eulerian circuit using edges of match and MST
remove repeated vertices of E
return E