Hi,<br><br>I created a wiki page for APSP here: <a href="https://github.com/pgRouting/pgrouting/wiki/APSP">https://github.com/pgRouting/pgrouting/wiki/APSP</a><br><br>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.. :)<br>
<br>We can put up any new idea there and discuss it here so that the overall draft keeps getting refined. <br><br><div class="gmail_quote">On Thu, Dec 2, 2010 at 1:59 PM, Daniel Kastl <span dir="ltr"><<a href="mailto:daniel@georepublic.de">daniel@georepublic.de</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class="gmail_quote"><div class="im"><div> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); 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/%7Ejwicks/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><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 class="im"><div> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); 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><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" target="_blank">https://github.com/pgRouting/pgrouting/wiki</a></div>
<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>
<br>_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
<br></blockquote></div><br><br clear="all"><br>-- <br>Regards,<br>-Jay Mahadeokar<br><br>