Re: [Boost-users] dijkstra-example.cpp

Subject: Re: [Boost-users] dijkstra-example.cpp
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-01-27 20:41:51

On Fri, 27 Jan 2012, Kunzman, Douglas (Doug) wrote:

> The tree that result from calling dijkstra's algorithm does not result 
> in a each vertice have at least one black edge reaching it.  I would 
> assume something is wrong?  Can someone offer some suggestions?

Each vertex (other than the start node itself) that is reachable from the 
start node should have exactly one black edge to it, at least in the 
directed case.  Do you have graphs that produce different behavior than 
that?

-- Jeremiah Willcock

>
> -----Original Message-----
> From: boost-users-bounces_at_[hidden] [mailto:boost-users-bounces_at_[hidden]] On Behalf Of Jeremiah Willcock
> Sent: Friday, January 27, 2012 4:18 PM
> To: boost-users_at_[hidden]
> Subject: Re: [Boost-users] dijkstra-example.cpp
>
> On Fri, 27 Jan 2012, fergie wrote:
>
>> I’ve been reviewing the dijkstra-example.cpp that is provided as part
>> of boost Graph.  I think I understand most of it and have been able to
>> demonstrate the application working to my boss.  I have one question
>> about the code.  When output the .dot file near the end of the program
>> the results are shaded either grey or black.  What is the significance
>> of the black and grey lines?
>
> Black lines are edges in the single-source shortest path tree, while gray lines are edges that are not in the tree.  Look at http://www.cs.cmu.edu/~avrim/451/lectures/lect1008.pdf for exactly what the tree represents.
>
>> I’ve looked through the documentation and am also confused about the
>> source and the target since we have an iterator going through the
>> entire graph.  What defines a source and target vertex?
>
> The graph is directed, so each edge goes from a defined source to a defined target.  The arrows in the output file show the directions of the edges.
>
> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>