Re: [Boost-users] [BGL] premature termination in dijkstra using visitor

Subject: Re: [Boost-users] [BGL] premature termination in dijkstra using visitor
From: Michael Fawcett (michael.fawcett_at_[hidden])
Date: 2009-10-02 11:47:59

On Fri, Oct 2, 2009 at 9:42 AM, Ralf Goertz
<R_Goertz_at_[hidden]> wrote:
> Hi,
>
> I have some very large undirected graphs (half a million vertices).
> Edges have weight 0 or 1. For each vertex I need to find all vertices
>
> Â  Â  Â  Â * that are in sum 2 edges away
> Â  Â  Â  Â * whose distance is 0
>
> Both tasks can be done with breadth-first searches but I don't know in
> advance how many edges in depth I have to traverse. That's why I thought
> of Dijkstra's algorithm. But in my case this is overkill as I am not
> interested in the exact distance of a vertex from a given vertex but
> only in if it is not farther than 0 or 2 away. Is it possible to use a
> visitor to alter the colormap to mark vertices as final that are too far
> even thought they are not final yet?

I don't have a suggestion, but I did want to lend weight to your
question since I have exactly the same requirements.  I currently use
Dijkstra and accept the overkill, but as my graphs get bigger it's
becoming less acceptable.

--Michael Fawcett