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

From: Dmitry Bufistov (dmitry_at_[hidden])
Date: 2006-05-11 11:43:24

Greg Link wrote:

> 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)
If every time your delays being changed at the same value, then you 
probably don´t need to rerun shortest pathes algorithm every time, you 
just can recalculate all you shortest-pathes trees in linear time as 
described here
http://arxiv.org/PS_cache/cs/pdf/0205/0205041.pdf
(Note sure that even in this case it will increase perfomance, but if 
you are really concerned about it then you can try)
--dima