[pgrouting-dev] APSP Implementation
daniel at georepublic.de
Thu Dec 2 21:44:49 EST 2010
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!
2010/12/2 Jay Mahadeokar <jai.mahadeokar at gmail.com>
> I created a wiki page for APSP here:
> 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
>>> 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:
>> 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.
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
> -Jay Mahadeokar
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
Georepublic UG & Georepublic Japan
eMail: daniel.kastl at georepublic.de
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the pgrouting-dev