Reflections on Shortest Paths

Structure of shortest paths

In this lesson, we reflect on the structural properties of shortest paths, as well as the sub-digraphs formed by putting together other shortest paths. We take a look at some examples to intuit better.

Nonuniqueness of shortest paths

There may be more than one shortest path between two vertices. For example, there are two〈s, x〉 and〈s, u, v, x〉 different shortest paths from $s$ to $x$ and three〈s, u, v, w〉, 〈s, x, w〉, and 〈s, u, v, x, w〉 different ones from $s$ to $w$.