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

Subject: [Boost-users] dijkstra_shortest_paths between sets of nodes (between polygons on a grid)
From: Stuck Developer (stuckdeveloper_at_[hidden])
Date: 2011-09-10 14:09:48

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

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.

Any smart solutions to this problem?