Traversing weighted graph through all vertecies ending up at the same point

Question

Is there an algorithm that will allow me to traverse a weighted graph in the following manner?

• Start at a specific node
• Go through all vertecies in the graph
• Do this in the least amount of time (weights are times)
• End up at the starting node

Answer 1

Sounds like the Travelling Salesman Problem to me. An NP-hard problem. There is no polynomial time algorithm that will give you the optimum solution. You could use a search heuristic to get a close to optimal solution though.

Answer 2

I am not sure, if any efficient algorithm exists, but a brute force approach would surely give you the answer.

In any case, can you give the constraints on the number of vertices/edges.

Answer 3

As Greg Sexton stated before me, it is a classic example of the Travelling Salesman Problem. There are many advanced algorithms about for handling this style of problem, which is best for your particular situation rather depends on the graph. If the number of vertices is high, you will need substantial computational power to get it done within a realistic time frame.