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

Subject: Re: [Boost-users] dijkstra-example.cpp
From: Kunzman, Douglas (Doug) (DKunzman_at_[hidden])
Date: 2012-01-27 17:48:01

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?

Doug

-----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