[pgrouting-dev] APSP Implementation

[Daniel Kastl]

> 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
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20101202/349eac55/attachment.html