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.