[pgrouting-dev] APSP Implementation

[Stephen Woodbridge]

On 12/2/2010 12:08 AM, Daniel Kastl wrote:
>
>             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.

Yes, exactly. I'm not sure it requires a whole RFC, but we might want to 
add a wish list document to the RFC directory that would make it easy to 
add ideas to the wish list document.

I just looked at the RFCs and notice that we do not have one for the 
contraction highway algorithm. Did you notice that that was implemented 
for OSM? MoNav is the project.

-Steve