Skip to content

Files

Latest commit

91f6885 · Jan 6, 2015

History

History
15 lines (11 loc) · 488 Bytes

README.md

File metadata and controls

15 lines (11 loc) · 488 Bytes

2-approximation-TSP

Travelling salesman problem 2-approximation algorithm.

We first start with n randomized nodes which are all connected to each other.
We then use Prim's algorithm to create a Minimum Spanning Tree.
We then do a pre-order walk on the MST to get a tour.
Which gives us an approximate solution to the Travelling Salesman Problem.

Demo
https://gilbertls.github.io/2-approximation-TSP/

Coded by Gilbert Lavergne-Shank
http://gilbertls.com