Re: [boost] BGL and hamiltonian paths

From: Vladimir Prus (ghost_at_[hidden])
Date: 2002-08-16 09:47:23

Fernando Cacciola wrote:

> The problem (conceptually):
>
> Given a set of n geometric sites and a distance map with entries for each
> pair of sites; that is, given a weighted Kn;
> And given starting and ending sites (s,e).
> I need to find the sequence of sites from the s to e that passes through
> all the sites only once with the shortest step each; that is, I need to
> find a minimum weight Hamiltonian path from s to e.
>
> I don't have any Graph book at hand, so if my memory isn't failing me, this
> is essentially a matter of removing all but the lowest-weight out-edges
> from s and e; and then removing all but the two lowest-weight out-edges
> from all other vertices to form an euler graph, and finally doing a
> topological sort.

Probably *my* memory is failining me, but hamiltonian path is an NP-complete 
problem. You can't solve it using any polynomial algorithm.

As to your question: I don't know any algorithm in BGL which would enumerate 
all paths in a graph.

HTH,
Volodya