Finding a shortest cycle

0
votes

Basically, I need to have a shortest path in a graph that covers all of the vertices and returns to the source. Repetition of any vertex is ok so long as it is the shortest path.

My algorithm starts from the source. I run a dijkstra algorithm to find the shortest path. Then I choose the smallest weighted unreached vertex and run the dijkstra again as the chosen vertex as the source and keep doing it until all vertices are done. Then from the last vertex use dijkstra again to find the shortest path back to the original source.

I tried, but it seems to fail and I cannot find the reason.

2
graphcycledijkstra
This problem is NP-complete, as it provides a hamiltonian cycle if any exists. Such a cycle would indeed be minimal. Do you need the exact minimum ? - Vincent Nivoliers
Take a look at en.wikipedia.org/wiki/Travelling_salesman_problem. Your problem is a relaxed version of Traveling Salesman Problem. - darksky

2 Answers

1
votes

Google the travelling salesperson problem,that finds the shortest cycle starting from the source covering all the vertices.The code for travelling salesperson is also not difficult to implement.

0
votes

Since any vertex can be visited more that once you are basically looking for the shortest closed walk in a graph. The problem with your approach is that dikstra will only find the shortest path from the chosen node back to the source . This will produce a star type solution, where you have multiple paths coming out of the source vertex. Which could be longer then a walk.

This is an NP problem, as Vincent stated, but you could try implementing it using a random walk algorithm. Or look at the Traveling Salesman Walk Problem (http://dspace.mit.edu/handle/1721.1/33668)