Introduction To Algorithms 2Nd Edition Incl Exercises Edition [Electronic resources] نسخه متنی

Cycles

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 = 〈v₀, v₁,..., v_k〉 is a path and c = 〈v_i, v_i+1,..., v_j〉 is a positive-weight cycle on this path (so that v_i = v_j and w(c) > 0), then the path p' = 〈v₀, v₁,..., v_i, v_j+1, v_{j +2},..., v_k〉 has weight w(p') = w(p) - w(c) < w(p), and so p cannot be a shortest path from v₀ to v_k.

That leaves only 0-weight cycles. We can remove a 0-weight cycle from any path to produce another path whose weight is the same. Thus, if there is a shortest path from a source vertex s to a destination vertex v that contains a 0-weight cycle, then there is another shortest path from s to v without this cycle. As long as a shortest path has 0-weight cycles, we can repeatedly remove these cycles from the path until we have a shortest path that is cycle-free. Therefore, without loss of generality we can assume that when we are finding shortest paths, they have no cycles. Since any acyclic path in a graph G = (V, E) contains at most |V| distinct vertices, it also contains at most |V| - 1 edges. Thus, we can restrict our attention to shortest paths of at most |V| - 1 edges.