CODEWITHSUNDEEP
c#algorithmpath
user2643346
user2643346

Reputation: 13

Checking for optimal path

I'm trying to find out if the algorithm i wrote returns the most optimal path for visiting every node in a graph. I'm trying to traverse the graph like you would mow a lawn or clean your house with a vacuum cleaner, or plow a field. I get a path back but is there a way to check if its the most optimal. Is there an API or online service that i could use to check it?

Ive looked at Dijkstra and A* algorithms as well as BFS and DFS but I'm not sure how to validate the path i get is the most efficient.

Given a graph how do i find the quickest and most efficient path that visits all the nodes?

Thanks

Upvotes: 0

Views: 201

Answers (1)

Jack Hopkins
Jack Hopkins

Reputation: 73

Unfortunately this in an NP Hard problem known as the travelling salesman problem.

There is therefore no known polynomial time solution. To traverse the entire solution space would take !N iterations (where N is the number of nodes). However, there are several solutions which can give you GOOD solutions, if not the best.

I would look into Simulated Annealing as a method to get a short path between all nodes.

http://en.wikipedia.org/wiki/Simulated_annealing

Upvotes: 2

Related Questions