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 12:10:50

On Fri, Oct 2, 2009 at 11:59 AM, Jeremiah Willcock <jewillco_at_[hidden]> wrote:
> On Fri, 2 Oct 2009, Michael Fawcett wrote:
>
>> On Fri, Oct 2, 2009 at 11:50 AM, Jeremiah Willcock <jewillco_at_[hidden]>
>> wrote:
>>>>
>>>> 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?
>>>
>>> The normal technique for this is to write a visitor that throws an
>>> exception
>>> when the distance becomes too large. Â The task of finding distance-0
>>> vertices can also be done by BFS with a filtered_graph that only keeps
>>> weight-0 edges; that will automatically stop when all of the needed
>>> vertices
>>> are found.
>>
>> Wouldn't throwing an exception when the weight gets too large mean the
>> search stops at the first vertex when distance > N? Â The OP wants all
>> vertices where distance == 2.
>
> Yes, so stop when the distance is at least 3; vertices are processed in
> order of distance.

Whoops, forgot that Dijkstra uses a priority queue (or similar).
Thanks for the reminder!

--Michael Fawcett