Date: 2000-01-12 21:27:48
Dave Abrahams writes:
> > Just to make sure I know at a high level what the algorithm is
> > suppose to do:
> > Do a best-first-search, and copy the resulting tree to a new graph?
> No, do a best-first-search and copy the original graph to a new graph. The
> new graph should be an excact copy of the original, except the nodes are
> labelled with their least total cost from the start node.
> the point is that in a best-first-search, each edge is only traversed once.
> This makes it appropriate for copying the graph, too.
But such a search algorithm will only hit the *reachable* nodes of the
graph from the starting vertex, so it would not be appropriate for
copying some graphs...
In any case, I'm working on it :)
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk