Re: [Boost-users] [BGL]: Highest performance graph-type available?

From: Michael Fawcett (michael.fawcett_at_[hidden])
Date: 2006-05-11 11:13:31

On 5/11/06, Greg Link <link_at_[hidden]> wrote:
>         I've got a 2D grid-structure, of some size "n x n". Each point in
> the grid is connected to it's four neighboring and adjacent cells in
> the grid by an edge. The edges (and their weights) represent the
> delay to travel between those two points in the grid. The weight of
> the edges is non-uniform, and determined at run-time.
>
>         I have a set of  {X1,Y1} and {X2,Y2} pairs that I want to find the
> shortest path between.

Have you looked into using the A* search?  I'm not a BGL expert, but
since you are working on a grid, you should probably just be using an
implicit graph.  I think there is mention of that in the A* BGL docs.
You can calculate your neighbors given your current position and the
offset to the neighboring grid cells.  That way you would only be
allocating nodes that were actually worth looking at.

HTH,

--Michael Fawcett