[pgrouting-dev] APSP Implementation

[Jay Mahadeokar]

Hi,

I created a wiki page for APSP here:
https://github.com/pgRouting/pgrouting/wiki/APSP

I have tried to put down some ideas already discussed on this thread. Please
go on and modify the page if I have missed something. Again, I dont have
experience with standard docs, so page would need a lot of restructuring I
guess..   :)

We can put up any new idea there and discuss it here so that the overall
draft keeps getting refined.

On Thu, Dec 2, 2010 at 1:59 PM, Daniel Kastl <daniel at georepublic.de> wrote:

>
>
>> Hey.. The dijextras algo should be able to provide solution for single
>> source shortest paths to all other points (1 to n points). The boost doc
>> here:
>> http://www.cs.brown.edu/~jwicks/boost/libs/graph/doc/dijkstra_shortest_paths.html<http://www.cs.brown.edu/%7Ejwicks/boost/libs/graph/doc/dijkstra_shortest_paths.html>
>> states that: "If you provide a distance property map through the
>> distance_map() parameter then the shortest distance from the source
>> vertex to every other vertex in the graph will be recorded in the distance
>> map. Also you can record the shortest paths tree in a predecessor map: for
>> each vertex *u in V*, *p[u]* will be the predecessor of *u* in the
>> shortest paths tree "
>>
>> So, I think there is no need for doing APSP / Warshall O(n^3) time for
>> this purpose, Dijextra will do that in O(m+nlog n). I am not fully aware of
>> the pgRouting dijextra implementation, does it provide above functionality?
>>
>
> Well, for the case 1:n you're right. This would be Dijkstra.
> I thought about cases like 2:n or more ... just I thought what if n and m
> are not the same.
> But I can't say this is possible with Warshall or any other algorithm. It's
> just some brainstorming
>
>
>>
>>
>> *One more thing:* Can we have a wiki page or something like that where we
>> can put up our ideas, and we can keep on modifying the draft as the ideas
>> are refined? I guess there are too many ideas in this thread and I am
>> finding some difficulty to keep track of all of them all..  Just a
>> suggestion :)
>>
>
> True. This thread is turning to be too long already.
>
> I enabled the Wiki addon for the pgRouting repository on GitHub:
> https://github.com/pgRouting/pgrouting/wiki
> Let me know if you can access. Maybe you need some user account for GitHub
> and maybe I have to give you permissions ... I haven't tried it yet.
>
> Daniel
>
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>


-- 
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20101202/f3e688e3/attachment-0001.html