[pgrouting-dev] APSP Implementation

[Stephen Woodbridge]

On 12/1/2010 11:01 PM, Daniel Kastl wrote:
> Hi Anton,
>
> I think there will be both cases. DARP/TSP might only need the matrix at
> first. But when you got your optimized tour result you had to run again
> the shortest path search to retrieve a path, which causes two problems:
>
>     * The network (conditions) might have changed if you run those path
>       queries later.

I guess this assumes the you are getting live feed data for traffic or 
something like that. What are you think here? Also be aware that the 
algorithms can select any of equal distance alternatives and the later 
if you single shortest path it might pick a different path, which may or 
may not be problematic.

>     * It might be slower to later run single shortest path queries again
>       independently

It would be interesting to enhance our single shortest path to be able 
to extract multiple single shortest paths based on a single graph build. 
So input might be something like

id, from, to
1, 27, 42
2. 101, 502
...

and the results would be

id, seq, from, to

> So an option to return only the distances or together with the path
> would be best in my opinion.
> Actually the distance would be just the length of the path, so that
> looks like "ST_length(path_geom)" to me. No?

I think we really need to get back a list of node or edges for the path 
not just a geometry. We can construct the geometry from the node list, 
but it is much harder to construct the node list from the geometry.

-Steve

> Daniel
>
>
>
>
> 2010/12/2 Anton Patrushev <anton.patrushev at georepublic.de
> <mailto:anton.patrushev at georepublic.de>>
>
>     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.
>
>     Anton.
>     _______________________________________________
>     pgrouting-dev mailing list
>     pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
>     http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
>
>
> --
> Georepublic UG & Georepublic Japan
> eMail: daniel.kastl at georepublic.de <mailto:daniel.kastl at georepublic.de>
> Web: http://georepublic.de <http://georepublic.de/>
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev