Re: dijkstra_shortest_paths with undirectedS example

From: David Abrahams (dave_at_[hidden])
Date: 2003-04-22 20:43:42

"jfw1000" <jfw1000_at_[hidden]> writes:

> Thanks, Michael, I knew that I misunderstand the problem,  the 
> results from the code is correct.
>
> O.K., let me explain my problem, and I would appreciate for any hints 
> and help.
>
> Suppose that I have a number of points(node), I know their distance
> (weight), and I know the starting point, how could I get the shortest 
> path passing all the these points or some of these points? Any 
> algorithm I can use in BGL?

Hah!  Classic travelling salesman problem!  NP complete!

Well, if you have a big graph any algorithm which actually finds the
shortest path is going to be SLOW.  However, there are some
interesting heuristic algorithms out there which do pretty well.

Just google for "travelling salesman" and have fun exploring.

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com