CODEWITHSUNDEEP
algorithmgraphtraversal
user400055
user400055

Reputation:

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?

Upvotes: 1

Views: 433

Answers (3)

Orbling
Orbling

Reputation: 20612

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.

Upvotes: 1

Greg Sexton
Greg Sexton

Reputation: 9289

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.

Upvotes: 7

Shamim Hafiz - MSFT
Shamim Hafiz - MSFT

Reputation: 22124

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.

Upvotes: 0

Related Questions