Problem in finding Hamiltonian circuit for TSP problem

Question

Hi there Im working on a project which needs to solve the TSP problem. The thing i need here is that how i can find the Hamiltonian circuits in the graph. In fact I know how to do this in the real world. But in the implementation and on the source code I do not know how this can be done. I have read articles on the internet which use some nested loops but i did not get what each for does and how the whole story goes on. I would be appreciating if someone can help me on this. And give me a simple example on how to implement this. I do not need a working model. Just assume that we have an array of vertices and an array of paths (by path I mean the start and end vertices of the path). How we can solve this problem.

Answer 1

One of the more efficient ways to find an exact solution to TSP is using a dynamic programming algorithm which runs in O(n^2*2^n). It is rather simple in comparison to some of the linear programming alternatives. Search "TSP dynamic programming" and you'll surely find a lot of examples.

There are more naive approaches, such as brute force which run in O(n!). If you saw a lot of for loops (ie: more than two) this is likely the type of algorithm that you have seen before. These will get the job done (maybe not in this lifetime, depending on the size of your graph).