0
$\begingroup$

From Introduction to Algorithms by Cormen et al:

We are given a directed graph G = (V,E) and vertices ${u,v}\in V $ and then the define Unweighted shortest path to be :

Find a path from u to v consisting of the fewest edges . Such a path must be simple , since removing a cycle from a path produces a path with fewer edges.

I know what simple path means . I think it means that basically no edges will be repeated in the path from u to v but what does "removing a cycle from a path produces a path with fewer edges" mean ?

1 Answers 1

2

Simply speaking, if we have vertices v1, v2, v3, v4, v5... and our path contains a cycle eg v1 -> v2 -> v4 -> v3 -> v2 -> v5 we can travel from v1 -> v5 over fewer edges by eliminating the cycle v2 -> v4 -> v3 -> v2, leaving the path v1 -> v2 -> v5