[pgrouting-dev] APSP Implementation

[Daniel Kastl]

Hi Jay,

Thank you for adding the Wiki page.
So there was no restriction? No permission problem to add or edit a
page? That's fine then.

I formatted the page a little bit for readability (no content changes).
Anyone else who wants to make some additions or changes, please go ahead!

Daniel



2010/12/2 Jay Mahadeokar <jai.mahadeokar at gmail.com>

> 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
>
>
> _______________________________________________
> 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/20101203/d7d61c09/attachment.html