[pgrouting-dev] APSP Implementation

[Daniel Kastl]

>
>
>> 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.
>
>
I actually don't assume live feed data but the fact that pgRouting keeps the
network in a database and it's possible to change attributes for example,
that are part of your cost parameter, at any time. Or maybe road links
become unavailable during a long APSP query.

I think the library should ensure that when you make a query it reads the
network data available at that time. If the query for processing a huge
distance matrix takes one hour for example, but makes steadily new requests
to the database, it could happen that some attributes change over time.
Whether this is problematic for an application or not depends on the
application. In most cases it probably isn't, that's true. But pgRouting
isn't limited to road networks, so who knows what kind of applications will
make use of it.



>     * 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
>

This would be the same as k-Shortest Path, right?
http://www.pgrouting.org/rfc/rfc-04.html
<http://www.pgrouting.org/rfc/rfc-04.html>

Daniel



-- 
Georepublic UG & Georepublic Japan
eMail: daniel.kastl at georepublic.de
Web: http://georepublic.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20101202/f46b9e84/attachment.html