4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It's just saying that you only need to use the recurrence relation up to $n-1$, since if there was a shorter length $n$ walk, you'd have a negative cycle. $\endgroup$ – Louis Aug 8 '17 at 8:22
  • $\begingroup$ What are "This statement" and "above recurrence relation"? Could you label or number them? $\endgroup$ – fade2black Aug 8 '17 at 8:24
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.