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
utovconsisting 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 ?
Simply speaking, if we have vertices
v1, v2, v3, v4, v5... and our path contains a cycle egv1 -> v2 -> v4 -> v3 -> v2 -> v5we can travel from v1 -> v5 over fewer edges by eliminating the cyclev2 -> v4 -> v3 -> v2, leaving the pathv1 -> v2 -> v5