Traveling Salesman Problem

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

Points: 0

Path:

Total Distance: