In my first use of the boost library, I'm using the BGL's dijkstra_shortest_paths algorithm to try and (obviously) find the shortest path between two points. I am then iterating along the shortest path to a given node to find the total path weight along that path. I compare this value to the path weight along a manhattan path, and find that the manhattan path is shorter. Rather than claim this is a problem with boost (yet), I'm at first believing it's my interpretation of the library. If I've piqued your interest, feel encouraged to read on. My graph is a representation of a 2-dimensional mesh, so I've got an NxN graph, where the vast majority of nodes have out-edges in all four directions (N,S,E,W), and in-edges in all four directions. I generate the graph with the following: typedef adjacency_list < listS, vecS, undirectedS, no_property, property < edge_weight_t, double > > graph_t; graph_t gGraph(num_nodes); then iterating over each node (i) and adding edges as follows: add_edge(i, easterlydest, easterlyweight, gGraph); finally, I call: dijkstra_shortest_paths(gGraph,sourcenum,predecessor_map(&p [0]).distance_map(&d[0])); to evaluate the shortest paths. (Note that much of this is a cut-and- paste from the Dijkstra_shortest_path example found at http:// www.boost.org/libs/graph/example/dijkstra-example.cpp ) Note also that my understanding of the last argument to dijkstra_shortest_paths is probably my weakest part of understanding the library. I then iterate along a given shortest path by using the following loop structure: while(node != sourcenum) // iterate from dest to source, summing as you go { int u = p[node]; int v = node; graph_traits < graph_t >::edge_descriptor e = edge(u,v,graph).first; double this_weight = get(edge_weight,graph,e); path_length += this_weight; node = p[node]; } This returns a value of 1309.16 as the total path weight. I then attempt to determine the manhattan path weights as well, to compare how much of an improvement the shortest path is to the manhattan paths. I attempt to traverse the manhattan paths using a similar approach, with something similar to the following (irrelevant lines omitted): while(node != destnode) // iterate from source to dest, iterating as you go { int nextnode = get_nextnode(xfirst,node); // gets index of next node in an x-first y-next manhattan path int u = node; int v = nextnode; graph_traits < graph_t >::edge_descriptor e = edge(u,v,graph).first; double this_weight = get(edge_weight,graph,e); xfpath_length += this_weight; node = nextnode; } When this runs, I get a path length of 1299.79, a value more than 0.1% smaller. Either I'm determining the manhattan and shortest path weights incorrectly, or it's not actually finding the shortest path. So I did a bit of debugging (as programmers are wont to do). Tracing the paths themselves, I eventually find that at one point, the shortest path (hereafter abbreviated DSP) chooses to follow an out- edge that doesn't have minimum weight. This is perfectly reasonable, as it's possible (and probable) that this choice made now, will have greater returns later, allowing an overall shorter path. However, it never again returns to even equality with the manhattan path - the manhattan path is shorter along the entire length, to the end. I've checked my corner cases, and the paths are only being summed along relevant edges (no off-by-one errors that I can see, at least). If anyone has any ideas on how I might best debug/change my code, or a means by which I can perform some other test, I'd love to hear it. If anyone needs any more information, the code is by no means confidential (though a bit messy) and I've got both .dot (graphviz) format and an svg representation of the graph available. My development platform is currently Mac OS X 10.4.4 PPC using Xcode, if it matters to anyone. Thanks, and I hope you don't mind the rather lengthy post! - Greg Link ---- 20 70 80 95 106