Menu
Yes Dijkstra's always gives shortest path when the edge costs are all positive. However, it can fail when there are negative edge costs.
Dijkstra's algorithm works correctly, because all edge weights are non-negative, and the vertex with the least shortest-path estimate is always chosen. In the first iteration of the while loop in lines 3 through 7, the source s is chosen and its adjacent vertices have their est(v) set to w((s, v)).
The predecessor map records the edges in the minimum spanning tree. Upon completion of the algorithm, the edges (p[u],u) for all u in V are in the minimum spanning tree. If p[u] = u then u is either the source vertex or a vertex that is not reachable from the source.
I have a need to use the Boost library to get the shortest path from one point to another. I've looked over the example code and it is decently easy to follow. However, the example only shows how to get the overall distances. I'm trying to figure out how to iterate over the predecessor map to actually get the shortest path and I can't seem to figure it out. I've read these two questions on the subject:
Dijkstra Shortest Path with VertexList = ListS in boost graph
Boost:: Dijkstra Shortest Path, how to get vertice index from path iterator?
But in both of the examples provided, the IndexMap typedef doesn't seem to work with the Visual Studio compiler and, frankly, Boost typedefs are a little confusing to me and I'm having some trouble figuring all of this out. Based on the Boost example code here, could anyone tell me how I can just get the path out of it? I would be very thankful.
http://www.boost.org/doc/libs/1_46_1/libs/graph/example/dijkstra-example.cpp
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With