From: jsiek_at_[hidden]
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 :)