<div class="gmail_quote"><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="gmail_quote"><div>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: <a href="http://www.cs.brown.edu/~jwicks/boost/libs/graph/doc/dijkstra_shortest_paths.html" target="_blank">http://www.cs.brown.edu/~jwicks/boost/libs/graph/doc/dijkstra_shortest_paths.html</a> states that: "If you provide a
distance property map through the <tt>distance_map()</tt> 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
<i>u in V</i>, <i>p[u]</i> will be the predecessor of <i>u</i> in
the shortest paths tree "<br><br>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?<br>
</div></div></blockquote><div><br></div><div>Well, for the case 1:n you're right. This would be Dijkstra.</div><div>I thought about cases like 2:n or more ... just I thought what if n and m are not the same.</div><div>
But I can't say this is possible with Warshall or any other algorithm. It's just some brainstorming</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="gmail_quote"><div>
<br><br><b>One more thing:</b> 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 :)<br>
</div></div></blockquote><div><br></div><div>True. This thread is turning to be too long already.</div><div><br></div><div>I enabled the Wiki addon for the pgRouting repository on GitHub: <a href="https://github.com/pgRouting/pgrouting/wiki">https://github.com/pgRouting/pgrouting/wiki</a></div>
<meta http-equiv="content-type" content="text/html; charset=utf-8"><div>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.</div>
<div><br></div><div>Daniel</div><div><br></div><div><br></div><div><br></div></div>