Single source shortest path problem

Characterizations about optimal shortest paths

Let’s prove some observations about what characterizes a shortest path.

Given a shortest path $s\to v$, this path is simple. If there exists a loop, then we can remove an edge in the loop. The path remains connected, and the weight can only decrease.

• If the cycle has positive weight edges, removing the cycle does decrease overall weight.
• A cycle with zero-weight edges can be arbitrarily removed, and the weight doesn’t increase. So, keep removing such cycles from the path until it’s simple.

Let $p$ be a shortest path $s\to v$, and $p^{\prime }:s\to u$ be a subpath. Then, $p^{\prime }$ is also a shortest path. Use an Exchange argument here: assume $p^{\prime }$ is not a shortest path for $s\to u$. Then, we can exchange it with another path $s\to u^{\prime }$ that has less weight, which means $p$ can only decrease in weight. This is a contradiction (we assume $p$ is shortest path), so $p^{\prime }$ must be the shortest path to begin with.

Generalizing the input increases runtime

There are a number of algorithms that solve this problem for increasingly general input cases. The tradeoff, however, is that the runtime also increases.

Here, we are generalizing on the type of input graph. We can also generalize the problem itself to find the shortest path between all vertex pairs in a graph.

Directed versus undirected input graphs?

It doesn’t matter whether the input graph is directed or undirected for any of the three algorithms below. If undirected, we simply treat each bidirectional edge as two directed edges.

Most basic graph

Arguably the main purpose of BFS is not for finding the shortest path. However, the BFS tree it produces, rooted at source $s$, also works for this purpose.

Fastest runtime, but only works correctly for unweighted graphs.

Handling edge weights (that are non-negative)

The first generalization is being able to handle graphs where edges have different weights. In a sense, BFS treated all edges as having the same weight, so Dijkstra’s algorithm will be able to handle more graphs correctly.

Stopping on negative weight cycles

Dijkstra’s runs infinitely when edges have negative weights. The Bellman-Ford algorithm is able to detect if a negative weight cycle is reachable from $s$, and successfully exits. However, runtime is drastically increased, to $O(mn)$.