[pgrouting-dev] APSP Implementation

[Daniel Kastl]

Hi Steve,

I don't have enough time unfortunately to catch up with the number of ideas
... also I'm missing technical expertise for some RFC's ;-)
That's why I collected them here as a reminder:
https://github.com/pgRouting/website/issues (not sure "website" repository
is the right place though)

I heard about some implementation, but don't really remember to have heard
about MoNav.

Daniel

<https://github.com/pgRouting/pgrouting/issues>

2010/12/2 Stephen Woodbridge <woodbri at swoodbridge.com>

> 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
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>



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