Re: [boost] BGL and hamiltonian paths

From: Fernando Cacciola (fcacciola_at_[hidden])
Date: 2002-08-16 10:26:50

----- Original Message -----
From: "Vladimir Prus" <ghost_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Friday, August 16, 2002 11:47 AM
Subject: Re: [boost] BGL and hamiltonian paths

> 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.
>
This is true for a general case.
My case however, uses a complete graph of n vertices (Kn), that is, a graph
in which every vertex is connected to all other vertices.
All complete graphs are hamilton connected.

Given that edges have weights, there should be a polynomial algorithm to
find the minimum hamiltonian path in a weighted complete graph.

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