[pgrouting-dev] APSP Implementation

[Daniel Kastl]

>
>
>>    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>
>>
>
> No, K-shortest paths is more like what google does when it gives you
> alternative routes. You start and end stay constant but you get the
> shortest, then the next shortest, etc
>
> I'm thinking of the case for example where you solve a TSP and now you want
> to extract the shortest paths from A-B, B-C, ... , Z-A and you only want to
> load and build the graph once but get back all the routes. You could
> probably think of it as via points. like start-A-B-C-D-end.
> You could run 5 separate queries to get all the route segments, or we could
> have a function that you pass it a set of path control points and it build
> one graph and resturns all the segments in one call. I thought you were
> referencing doing this in an earlier email. Regardless this would be much
> faster than dosing N separate queries and having to build the graph N times.
>
>
You mean you request a route including points in between and return them all
at once.
This makes sense, that's true. I think there are many possibilities for
addons. We should add it to the wishlist.

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/ff74103e/attachment-0001.html