Boost logo

Boost Users :

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
(Note sure that even in this case it will increase perfomance, but if
you are really concerned about it then you can try)

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at