Single-Source Shortest-Paths Problem

We’ll now present some algorithms for the single-source shortest-paths problem, where, given a weighted digraph $G$ and a vertex $s$, the goal is to find the shortest paths from $s$ to all other vertices. Since $s$ is the starting vertex of all of these paths, it is called the source vertex.

Note: Various shortest-paths algorithms typically employ weighted digraphs to model the underlying network.

Since the length of a shortest path in a weighted digraph is the sum of the edge weights along the path and not the number of edges in that path, BFS no longer suffices for finding the shortest paths.

Some of the well-known and lesser-known single-source shortest-paths algorithms capitalize on the idea of edge-relaxations, and a specific initialization scheme for vertex attributes that was originally proposed by Lester R. Ford Jr. We cover this important scheme here.

Conventions

The source vertex is typically denoted $\mathbb{s}$ unless stated otherwise.

Recall: A path from $s$ to $v$ is referred to as an $\mathbb{s} - \mathbb{v}$ path.

Attributes and initializations scheme

For each vertex $v$ of a weighted digraph $G$, we want to maintain the following attributes:

• $v.dist$ stores the length of a shortest $s - v$ path amongst all $s - v$ ...