A recursive solution to the all-pairs shortest-paths problem - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-22T06:42:31Z https://cs.stackexchange.com/feeds/question/79853 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/79853 4 A recursive solution to the all-pairs shortest-paths problem laura https://cs.stackexchange.com/users/67957 2017-08-08T08:13:19Z 2017-08-08T09:23:57Z <p>I am learning All pair Shortest Path from <a href="https://en.wikipedia.org/wiki/Introduction_to_Algorithms" rel="nofollow noreferrer">CLRS</a> book,but got stuck in the begining itself.I am writing my query.</p> <p>According to one of the <strong>Lemma</strong> of shortest path -:</p> <blockquote> <p>All Subpaths of shortest path are shortest.</p> </blockquote> <p>Using this lemma, we can write the <strong>Structure of shortest path</strong> given as-:</p> <blockquote> <p>Consider a shortest path $p$ from vertex $i$ to $j$ and suppose that $p$ contains atmost $m$ edges.We can decompose path $p$ into subpath $p^{'}$ i.e $ik\,\,(\,\,i\rightarrow\,\rightarrow k )$ and one edge $(k\rightarrow j)$ From the lemma it is clear that subpath $p^{'}$is also shortest and $p^{'}$ contains atmost $m-1$ edges. so we can write as</p> <blockquote> <p>$\delta\,(i,j)=\delta\,(i,k)+w(k,j)\label{eqn:1}$</p> </blockquote> </blockquote> <p>where $\delta\,(i,j)$=shortest path weight from $i$ to $j$</p> <p>Allright!!!! I am Ok till here.</p> <p>Now the Author has wriiten the <strong>recursive solution to all pair shortest path</strong> which too makes sense to me .It is given by-:</p> <blockquote> <p>$L_{i,j}^{m}$=<strong>Minimum weight of any path from vertex $i$ to vertex$j$ that contains atmost $m$ edges.</strong></p> <blockquote> <p>$L_{i,j}^{m}$=$min_{(1\,\leq k \leq n)}$$\,\,(L_{i,k}^{m-1}\,\,+w(k,j)\,\,)$ $\,\,\,(1)$</p> </blockquote> </blockquote> <p>Here $k$ is used to find out all the <strong>predecessors</strong> of $j$.</p> <p>I am still ok here,but i am stuck in the following point.</p> <blockquote> <p>If the graph contains no negative-weight cycles, then for every pair of vertices $i$ and $j$ for which $\delta(i,j)\leq \infty$(i.e <strong>connected</strong>)there is a shortest path from $i$ to $j$ that is simple and thus contains at most $n-1$ edges.A path from vertex $i$ to vertex $j$ with more than $n-1$ edge cannot have lower weight than a shortest path from $i$ to $j$ . The actual shortest path is given by </p> </blockquote> <p>$\delta(i,j)=L_{i,j}^{n-1}=L_{i,j}^{n}=L_{i,j}^{n+1}.... (2)$</p> <p>I am not getting relation between this statment$((1)\,\,and\,\,(2)\,)$ .Please help me out to derive this.</p> https://cs.stackexchange.com/questions/79853/-/79854#79854 3 Answer by fade2black for A recursive solution to the all-pairs shortest-paths problem fade2black https://cs.stackexchange.com/users/72943 2017-08-08T08:58:13Z 2017-08-08T09:23:57Z <p>(1) tells you how to compute the shortest path. </p> <p>Note that <strong>given that the graph has no negative-weight edge</strong>, the shortest path between two nodes is a simple path (with no cycles) which has at most $n-1$ edges. More than $n-1$ edges means a cycle which increases the path length. But we are interested in the shortest path. </p> <p>(2) claims that after $n-1$ edges the shortest path length remains same: $L_{i,j}^{n-1}=L_{i,j}^{n}$ is read as "the shortest path from $i$ to $j$ passing through $n-1$ edges is the same as the shortest path through $n$ edges".</p> <p>In fact it means that there is no need to compute $L_{i,j}^{n},L_{i,j}^{n+1},\dots$ since it will not lower the path between $i$ and $j$.</p>