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@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Jeremiah Willcock Sent: Friday, January 27, 2012 4:18 PM To: boost-users@lists.boost.org 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users