Re: [Boost-users] dijkstra_shortest_paths between sets of nodes (between polygons on a grid)

Subject: Re: [Boost-users] dijkstra_shortest_paths between sets of nodes (between polygons on a grid)
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-09-10 14:45:08

On Sat, 10 Sep 2011, Stuck Developer wrote:

> This ought to be a classic problem but I haven't found a solution yet...
>  
> Conceputally, I'm trying to find the shortest paths between all polygons within a maximum weighted distance over a grid of friction weights (as well as the total
> weighted distance of each of these shortest paths).
>  
> The grid with all the weights (a "friction" value representing the weight to move over that particular grid cell) is currently used to create a network with one
> vertex per grid cell and edges to its immediate eight neighbours (in the cardinal and diagonal directions). The weight of each edge is calculated to the average
> weight of the vertex and its neigbours in the four cardinal directions and multiplied by sqrt(2) in the diagonal directions to compensate for the longer euclidean
> distance.
>  
> Conceptually again, on this grid, there are a bunch of polygons. These are then made up ofcontiguous groups of vertices. Each polygon could thus be considered a
> set (or a component) of vertices with a unique id for each polygon.
>  
> The problem now is to find the shortest path over the weighted grid between the edges of all polygons within a maximum weighted distance from each other.
>  
> NOTE that the shortest path between two polygons should be able to pass through the weighted grid cells of other polygons along the way when these other polygons
> are not considered being source or target "vertex sets".
>  
> I first tried to solve this by looping through all of the polygons and finding the shortest path between some representative vertex (e.g. the centroid grid cell)
> inside a source polygon to a representative vertex within each possible target polygon. I did this by setting all of the grid cell weights to zero within each of
> the two polygons, running the dijkstra_shortest_paths between their representative vertices and then resetting the weights within these two polygons before
> solving it for another pair of polygons.
>  
> This actually works but the search goes bezerk within the polygons where all the edges have a cost of zero, and if these polygons are big enough, I run out of
> memory (I guess the shortest path becomes too long...).

You can give the internal edges some tiny (but non-zero) weight such that 
no path within a single polygon will be long enough to affect the overall 
results.

> I'm thinking this should be possible to solve by instead initializing 
> all of the vertices within each source polygon to "discovered" (i.e. 
> black) somehow and initializing the priority queue and the cost in some 
> corresponding manner. I just don't know how. Then there is the question 
> of knowing when the shortest path to the target polygon has been 
> reached... And thirdly if it would be possible to stop the search when a 
> maximum weighted distance has been reached.

You can initialize vertices to black and add them to the queue; see 
dijkstra_shortest_paths_no_init on 
<URL:http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/dijkstra_shortest_paths.html> 
for details.  Stopping the search is usually done by adding a visitor that 
throws an exception when a target distance (or a given vertex) is reached. 
You might also want to try A* search 
(<URL:http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/astar_search.html>) 
if you have a heuristic for estimating path lengths to target vertices. 
The example on that page shows how to terminate the search at a target 
vertex; libs/graph/example/astar_maze.cpp in the Boost source tree has 
another A* example.

-- Jeremiah Willcock