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$.

Concatenation of shortest paths

When a path terminates at a vertex, from which another one begins, we refer to the resulting digraph (consisting of the two paths) as being formed from the concatenation of those two paths. We might be tempted to think that concatenating a shortest path, starting at a vertex $u$, with another shortest path, ending at a vertex $v$, gives a $u-v$ shortest path but that’s not true. Let’s look at the following example.

Suppose we have a $v_1-v_3$ shortest path ...