[pgrouting-dev] APSP Implementation

[Stephen Woodbridge]

On 12/1/2010 10:50 PM, Anton Patrushev wrote:
> Hi list,
>
> Daniel is right - we mostly need a distance matrix, so I think there
> should be at least an option to return distance matrix only and omit
> extra work on extracting paths. Or should it be different function?
> It would be nice if extracted paths could be in form of phRouting
> 'path' type with additional 'from' and 'to' columns.

Agreed.

You can do a lot in the wrapper functions like joining to other tables 
or otherwise post processing the results that come back. The key to this 
is to have the necessary references to the other data.

I think Daniel made an excellent point earlier that I would like to 
hilite which is that we can build the graph once the process it multiple 
times in the code before we return the results.

So the process flow might look like this for a SOME PAIRS shortest path

build graph from bounding box
if num pairs is < some limit then
   loop thought pairs and solve shortest path
else
   use APSP algorithm
return results as:
from,to,distance[,array{from,node,node,...,to}]

or something like that.

A lot of good ideas.

-Steve