From: Fernando Cacciola (fcacciola_at_[hidden])
Date: 2002-08-16 09:02:37
I need to solve the following graph problem. I know how to do it by hand (I
think :-) but I was trying to figure out what would be the best approach
using BGL features. None of its algorithms seems to be of any help, but I
might be just missing it...
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.
I think I know how to do it by hand using a loop, out_edges() and
remove_edge(); but I was wondering if there was any shortcut.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk