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

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

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.

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.

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.