• Advertisement
Sign in to follow this  

traversing all the edges of a graph

This topic is 4308 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi there. I 've got a problem with my graph. I want to visit all the edges of my graph, covering the shortest distance. It doesn't matter if i visit an edge or a vertex more than one time, as long as the total distance you cover is the shortest one. I start from a vetrex and i finish in another one. I'have searched in the net and i found out that it is quite similar to the Chinese postman problem ( http://people.bath.ac.uk/tjs20/introduction.htm ) but all the solutions i found for the problem just test if there is A path that traverses all the edges of a graph; they don't find the shortest route. Could anyone help me out? Any ideas?

Share this post


Link to post
Share on other sites
Advertisement
Sounds more like the Traveling Salesman Problem. Just look for it on google (also try TSP as a keyword). You must be able to find useful articles in there.

Share this post


Link to post
Share on other sites
Yes it resembles the TS problem (which is np complete btw - so I hope you're not looking for a fast AND perfect solution). But TP isn't allowed to visit a graph point more than once.

If you want a fast solution you can look up some genetic algoritms (like SA - simulated Annealing) that deal with approximate solutions of the TS problem and refine the base function to fit your problem.

To get the perfect solution you'll need to check every possible combination. Depending on your graph this can be very slow.

Greetings, Roga

Share this post


Link to post
Share on other sites
I think that this problem is not NP-Complete (the Chinese postman problem is not ).

>If you want a fast solution you can look up some genetic algoritms (like SA - simulated Annealing) that deal with approximate solutions of the TS problem and refine the base function to fit your problem.

Approximate algorithms? But i want to be sure that my solution is 100% correct..

Share this post


Link to post
Share on other sites
Try this: http://www.uclic.ucl.ac.uk/harold/cpp

From what I've seen, the algorithm is general, and should work for arbitrary graphs.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement