Cycles

| < Day Day Up > |

#### 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 = 〈v0, v1,..., vk〉 is a path and c = 〈vi, vi+1,..., vj〉 is a positive-weight cycle on this path (so that vi = vj and w(c) > 0), then the path p' = 〈v0, v1,..., vi, vj+1, vj +2,..., vk〉 has weight w(p') = w(p) - w(c) < w(p), and so p cannot be a shortest path from v0 to vk.

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.

| < Day Day Up > |