Single-Source Shortest Paths
When you hear the term shortest path, you may think of the shortest physical distance between your current location and wherever it is you’re going. Finding the most optimal route via GPS is one of the most widely used mobile applications. Physical paths are not the only types we may wish to find a shortest path for. Other examples include:
- Network Routing: To improve network performance, it is critical to know the shortest path from one system to another in terms of latency.
- Puzzle Solving: For puzzles such as a Rubik’s cube, the vertices could represents states of the cube and edges could correspond to a single move.
- Robotics: Shortest paths in terms of robotics have a lot to do with physical distances, but it could also relate the completing a task efficiently.
These notes will cover classical single-source shortest path algorithms, but first we must formally define the problem.
Definition
Given a weighted, directed graph
The shortest-path weight between two vertices
where
The output of a shortest-path algorithm will produce, for each vertex
: The shortest-path estimate from to . : The predecessor of in the shortest path from to .
Shortest-path algorithms rely on an optimal substructure property that is defined by Lemma 22.1 (Cormen et al. 2022).
Lemma 22.1
Given a weighted, directed graph
with weight function , let be a shortest path from vertex to vertex . For any and such that , let be the subpath of from vertex to vertex . Then, is a shortest path from to .
It is also important to note here that a shortest path should contain no cycles. Some shortest-path algorithms require that the edge weights be strictly positive. For those that do not, they may have some mechanism for detecting negative-weight cycles. In any case, a cycle of any kind cannot be included in a shortest path. This is because if a cycle were included, we could simply traverse the cycle as many times as we wanted to reduce the weight of the path. For positive-weight cycles, if a shortest path included a cycle, then surely we could remove the cycle to get a lower weight.
As we build a shortest path, we need to keep track of which vertices lead us from the source to the destination. Some algorithms maintain this by keeping a predecessor attribute for each vertex in the path. Solutions such as the Viterbi algorithm keep an array of indices that correspond to the vertices in the path. In any case, we will need to keep track of the vertices in the path as we build it.
Relaxation
There is one more important property to define before discussing specific algorithms: relaxation. Relaxing an edge
def initialize_single_source(G, s):
for v in G.V:
v.d = float('inf')
v.pi = None
s.d = 0
When the values are changed, we say that the vertex has been relaxed. Relaxing an edge
def relax(u, v, w):
if v.d > u.d + w(u, v):
v.d = u.d + w(u, v)
v.pi = u
Properties
Relaxation has the following properties.
-
If the shortest-path estimate of a vertex is not
, then it is always an upper bound on the weight of a shortest path from the source to that vertex. -
The shortest-path estimate of a vertex will either stay the same or decrease as the algorithm progresses.
-
Once a vertex’s shortest-path estimate is finalized, it will never change.
-
The shortest-path estimate of a vertex is always greater than or equal to the actual shortest-path weight.
-
After
iterations of relaxing on all , if the shortest path to has edges, then .Following Introduction to Algorithms, we will first discuss the Bellman-Ford algorithm, which has a higher runtime but works with graphs that have negative edge weights. Then, we will discuss Dijkstra’s algorithm, which has a lower runtime but only works with graphs that have non-negative edge weights.
Bellman-Ford
The Bellman-Ford algorithm is a dynamic programming algorithm that solves the single-source shortest-paths problem in the general case in which edge weights may be negative. If a negative-weight cycle is reachable from the source, then the algorithm will report its existence. Otherwise, it will report the shortest-path weights and predecessors. It works by relaxing edges, decreasing the shortest-path estimate on the weight of a shortest path from
def bellman_ford(G, w, s):
initialize_single_source(G, s)
for i in range(1, len(G.V)):
for (u, v) in G.E:
relax(u, v, w)
for (u, v) in G.E:
if v.d > u.d + w(u, v):
return False
return True
Example
In the figure below, graph (a) shows the original graph before iterating over the edges. Graphs (b)-(e) show the result of looping over both edges originating from

Figure 1: Step-by-step execution of Bellman-Ford on a graph with negative-weight edges (Cormen et al. 2022).
Correctness
Bellman-Ford is guaranteed to converge after
Proof
The first iteration relaxes
for (u, v) in G.E:
if v.d > u.d + w(u, v):
return False
If there exists a negative-weight cycle
To complete the proof by contradiction, assume that Bellman-Ford returns True
. Then we would have that
Since the vertices are in a cycle, each vertex appears only once in each summation
This contradicts the assumption that there is a negative-weight cycle. Therefore, if Bellman-Ford returns True
, then there are no negative-weight cycles.
Analysis
Using an adjacency list representation, the runtime of Bellman-Ford is
Example 22.1-1
Run Bellman-Ford on the given path using

Figure 2: Figure 22.4 from (Cormen et al. 2022).
Shortest Paths on a DAG
If we are given a directed acyclic graph (DAG), we can solve the single-source shortest path problem in
def dag_shortest_paths(G, w, s):
initialize_single_source(G, s)
for u in topological_sort(G):
for v in G.adj[u]:
relax(u, v, w)
Example
Run dag_shortest_paths
on the graph given below with

Figure 3: Figure 22.5 from (Cormen et al. 2022).
Analysis
The runtime of dag_shortest_paths
is for
loop makes on iteration per vertex, and the inner loop relaxes each edge only once.
Dijkstra’s Algorithm
Dijkstra’s algorithm also solves the single-source shortest path problem on a weighted, directed graph
def dijkstra(G, w, s):
initialize_single_source(G, s)
S = []
Q = G.V
while Q:
u = extract_min(Q)
S.append(u)
for v in G.adj[u]:
prev_d = v.d
relax(u, v, w)
if v.d < prev_d:
decrease_key(Q, v)
Example
A Python example of the figure below is available here.

Figure 4: A step-by-step execution of Dijkstra’s algorithm on a graph with non-negative edge weights (Cormen et al. 2022).
Analysis
See Chapter 22 of Introduction to Algorithms for a detailed analysis of Dijkstra’s algorithm. Inserting the nodes and then extracting them from the queue yields