When reading about shortest paths in Cormen . I came across this paragraph which says that 'shortest path cannot contain' positive edge path even. But I don't understand the logic behind their explanation
Can a shortest path contain a cycle? As we have just seen, it cannot contain a negative-weight cycle. Nor can it contain a positive-weight cycle, since removing the cycle from the path produces a path with the same source and destination vertices and a lower path weight. That is, if p {vo,v1,v2,.... vk} is a path and c = {vi; v(i+1)....vj) is a positive-weight cycle on this path (so that vi = vj and w(c)> 0), then the path pnew = {v0,v1,.... vi, v(j+1) , ... vk} has weight w(pnew) = w(p)-w(c) < w(p), and so p cannot be a shortest path from v0 to vk.
The original snip from the book is here. enter image description here
Could someone explain why it is so ? I don't understand because any way removing an edge will cause the path length to decrease right ? why are they seeing removing positive edge cycle as different ?
For eg in the following diagram enter image description here
How are they removing cycle and connecting vi and v(j+1) ?
1 Answer 1
They are just saying that if $P$ is a shortest path, in $P$ there are not positive cost cycles, since removing the cycle would led to a smaller cost (and so to a better path).
Consider your example and suppose we want the shortest path beween $s$ and $v_k,ドル let $P=(s,v_1,\color{red}{v_i},\color{red}{v_{i+1}},\color{red}{v_{j-1}},\color{red}{v_i},v_{i+1},v_{j-1},v_{j+1},v_k)$.
Removing the cycle from $P$ we obtain $P'=(s,v_1,v_i,v_{i+1},v_{j-1},v_{j+1},v_k)$ where $cost(P')=cost(P)-6,ドル so to a better path in terms of cost.
Explore related questions
See similar questions with these tags.