CSC373H Lecture 3
CSC373H Lecture 3
September 22, 2021
Single-Source Shortest Paths
Today we’ll talk about the Single-Source Shortest Paths (SSSP)
problem.
▶ Input: connected, directed, weighted graph G = (V ,E ), with
n vertices and m edges; and start vertex s
▶ Each edge e has nonnegative weight w(e)
▶ Output: shortest path (i.e. path of minimum total weight)
between s and each other vertex
Remember Breadth-First Search?
▶ Breadth-first search (BFS) solves the SSSP problem in
unweighted graphs
▶ Here, we want to solve the problem on weighted graphs
▶ Hold on: can’t we just replace each edge of, say, weight q
with a path of q unweighted edges and then use BFS?
Dijkstra’s Algorithm
▶ Dijkstra’s algorithm solves the SSSP on weighted graphs
where all weights are nonnegative
▶ On each iteration of its loop, it finds the shortest path to one
new vertex
▶ There are several ways to implement the algorithm. We’ll
study three
1. Slow implementation that directly follows the algorithm
2. Faster implementation that replaces some work on edges with
smarter but equivalent work on vertices
3. Even faster implementation that uses a data structure from
CSC263!
Dijkstra’s Algorithm: Pseudocode
for all v in V:
d[v] = infinity # Shortest path to each vertex
X = {s} # Vertices whose shortest paths have been found
d[s] = 0
while X != V:
let (u*, v*) be an edge where u* in X and v* not in X
that minimizes d[u*] + w(u*, v*)
add v* to X
d[v*] = d[u*] + w(u*, v*)
▶ Define the Dijkstra score for edge (u, v) as d [u] + w(u, v)
▶ Notice at each step that Dijkstra’s algorithm is choosing the
edge leaving X that minimizes the Dijkstra score
▶ For that reason, we’ll call this a greedy algorithm
Dijkstra’s Algorithm: Example
Let’s run Dijkstra’s algorithm on this graph, using start vertex
s = 1.
1
2
12
3
6
4
45
5
7
26
9
2
8
21
Proof of Correctness
Let’s use induction to prove that the kth vertex added by
Dijkstra’s algorithm to X has the correct shortest path.
Notation: δ(x) is the shortest total path weight from s to x
Base case, k = 1
▶ The first vertex added to X is s, and we set its shortest path
to d [s] = 0
▶ Remember that we’re assuming that all edges have
nonnegative weight
▶ Therefore, there cannot be a path from s to s shorter than
the empty path
▶ That is, δ(s) = 0 = d [s], as required
Proof of Correctness…
Inductive case, k > 1
▶ IH: d [v ] = δ(v) for the first k − 1 vertices that Dijkstra added
to X
▶ Let v∗ be the kth vertex added to X
▶ Let (u∗, v∗) be the edge with minimum Dijkstra score
▶ Dijkstra’s algorithm assigns d [v∗] = d [u∗] + w(u∗, v∗)
▶ We have to show that d [v∗] = δ(v∗). We’ll do this in two
steps
Proof of Correctness…
First, we argue that δ(v∗) ≤ d [v∗]
▶ Because u∗ was already in X , the IH applies to it:
d [u∗] = δ(u∗)
▶ That is, there is a path from s to u∗ with length d [u∗]
▶ So, there is some path P from s to v∗ with length
d [u∗] + w(u∗, v∗) = d [v∗]
▶ P is just some path. The shortest path δ(v∗) can only be
shorter
Proof of Correctness…
Second, we argue that δ(v∗) ≥ d [v∗]
▶ We have to show that our path P of length d [u∗] + w(u∗, v∗)
is the shortest path from s to v∗
▶ Choose some other arbitrary competing path Q
▶ We know that Q starts at s and ends at v∗
▶ Because s is in X and v∗ is not, we also know that Q starts
inside X and ends outside of X
▶ So, at some point, Q must cross for the first time from inside
of X to outside of X on edge (y , z)
▶ Q therefore consists of three components: getting from s to
y , the edge (y , z), and getting from z to v∗
Proof of Correctness…
Q therefore consists of three components: getting from s to y , the
edge (y , z), and getting from z to v∗. Let’s add these up!
▶ Getting from s to y costs at least d [y ] (by IH)
▶ Taking the edge (y , z) costs w(y , z)
▶ And getting from z to v∗ costs at least 0 (because all edges
have nonnegative weight!)
Total length of Q is therefore at least d [y ] + w(y , z)
▶ Notice: this is at least the value of a Dijkstra score!
▶ This cannot be any less than the Dijkstra score that Dijkstra’s
algorithm chose, though, because Dijkstra chooses the
minimum Dijkstra score.
Therefore, Q is no shorter than the path P found by Dijkstra’s
algorithm.
Runtime
Let m be the number of edges and n the number of vertices in the
graph. Assume that the graph is represented as adjacency lists.
What is the most accurate runtime of Dijkstra’s algorithm if we
implement it directly, using our pseudocode?
▶ A. O(n2)
▶ B. O(m2)
▶ C. O(mn)
▶ D. O(m + n)
▶ E. O(n3)
The Path Itself
What if you want the actual shortest path itself, not just its length?
P = {} # edges in shortest paths tree
for all v in V:
d[v] = infinity # Shortest path to each vertex
P[v] = NIL # Predecessors on path
X = {s} # Vertices whose shortest paths have been found
d[s] = 0
while X != V:
let (u*, v*) be an edge where u* in X and v* not in X
that minimizes d[u*] + w(u*, v*)
add v* to X
d[v*] = d[u*] + w(u*, v*)
P[v*] = u*
Dijkstra’s Algorithm, Take 2
▶ Every edge in the graph has a Dijkstra score; Dijkstra’s
algorithm as we’ve written it has to check through all relevant
edges to find the minimum one
▶ Really, what we care about is the best Dijkstra score for each
vertex, not the Dijkstra score of each edge
▶ We can keep track of the best Dijkstra score for each vertex,
and then use the minimum one on each iteration
Dijkstra’s Algorithm, Take 2: Pseudocode
for all v in V:
d[v] = infinity # Shortest path to each vertex
X = {} # Vertices whose shortest paths have been found
d[s] = 0
while X != V:
choose vertex v* not in X such that d[v*] is minimum
add v* to X
for each vertex u not in X:
d[u] = min(d[u], d[v*] + w(v*, u))
Our Example Again
Let’s run our new implementation of Dijkstra’s algorithm on this
graph, using start vertex s = 1.
1
2
12
3
6
4
45
5
7
26
9
2
8
21
Runtime
Let m be the number of edges and n the number of vertices in the
graph. Assume that the graph is represented as adjacency lists.
What is the most accurate runtime of our new implementation of
Dijkstra’s algorithm?
▶ A. O(n2)
▶ B. O(m2)
▶ C. O(mn)
▶ D. O(m + n)
▶ E. O(n3)
Dijkstra’s Algorithm, Take 3
▶ On each iteration, we have to find the minimum of the
remaining d values
▶ Right now we’re stuck with linear search
▶ Hmm. Quickly finding the minimum. There’s a data structure
for this . . .
Dijkstra’s Algorithm, Take 3: Pseudocode
q = min priority queue
for all v in V:
d[v] = infinity # Shortest path to each vertex
enqueue all V in q
X = {} # Vertices whose shortest paths have been found
d[s] = 0
update priority of s in q
while X != V:
v* = dequeue minimum priority element from q
add v* to X
for each edge (v*, u) in q:
if d[u] > d[v*] + w(v*, u):
d[u] = d[v*] + w(v*, u)
update priority of u in q
Runtime
▶ We can use a min-heap to implement the priority queue of
vertices
▶ Initialization is O(n) to enqueue the n vertices
▶ The while loop does n dequeues, each of cost lg n
▶ The inner for-loop examines each of the m edges at most
once, and each edge costs O(lg n) if its distance is updated in
the queue
▶ So, we have O(n) + O(n lg n) + O(m lg n) = O(m lg n)