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

From: Greg Link (link_at_[hidden])
Date: 2006-05-11 11:07:39

Dima -
        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. The set is 'large'. Rather than running the  
standard dijkstra_shortest_path, and therefore having a run-time of O 
(num_pairs * V^2), I use johnson to find the all_pairs paths, at a  
cost of O(V*E*log(V)). Since E=2*V, that's effectively (V^2 log(V)).  
For any num_pairs > log(V), the johnson algorithm /should/ be faster.

        I do this a number of times (10 million), constructing a new graph  
each time, putting the edges in, and then solving the all_pairs  
paths. Profling the code shows that the graph construction is fairly  
trivial compared to the actual johnson algorithm (and the BFS_Visitor  
beneath that). Anything else that might help?

        Thanks for your interest,
- Greg

On May 11, 2006, at 10:53 AM, Dmitry Bufistov wrote:

> Greg Link wrote:
>> I'm using BGL for the johnson_all_pairs_shortest_path algorithm,
>> [snip]
>> and I'm wondering if that's the best choice. My graph has (E=2*V),
>> and all nodes are of constant degree, with 4 edges incident on them.
>
> Hi Grek,
> Probably there is better algorithm for your original problem).  
> Could you
> describe in brief it?
> Regards,
> --dima
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users