A recursive solution to the all-pairs shortest-paths problem

Question

I am learning All pair Shortest Path from CLRS book,but got stuck in the begining itself.I am writing my query.

According to one of the Lemma of shortest path -:

All Subpaths of shortest path are shortest.

Using this lemma, we can write the Structure of shortest path given as-:

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

$\delta\,(i,j)=\delta\,(i,k)+w(k,j)\label{eqn:1} $

where $\delta\,(i,j)$=shortest path weight from $i$ to $j$

Allright!!!! I am Ok till here.

Now the Author has wriiten the recursive solution to all pair shortest path which too makes sense to me .It is given by-:

$L_{i,j}^{m}$=Minimum weight of any path from vertex $i$ to vertex$j$ that contains atmost $m$ edges.

$L_{i,j}^{m}$=$min_{(1\,\leq k \leq n)}$$\,\,(L_{i,k}^{m-1}\,\,+w(k,j)\,\,)$ $\,\,\,(1)$

Here $k$ is used to find out all the predecessors of $j$.

I am still ok here,but i am stuck in the following point.

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 connected)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

$\delta(i,j)=L_{i,j}^{n-1}=L_{i,j}^{n}=L_{i,j}^{n+1}.... (2)$

I am not getting relation between this statment$((1)\,\,and\,\,(2)\,)$ .Please help me out to derive this.

Answer 1

(1) tells you how to compute the shortest path.

Note that given that the graph has no negative-weight edge, 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.

(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".

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$.