CSC 373 - Algorithm Design, Analysis, and Complexity Summer 2016

Lalla Mouatadid
Greedy Algorithms: Dijkstra’s Shortest Path Algorithm

Let G(V, E, w) be an edge weighted graph, where w : E → R+ . Let s, t be two vertices in G (think of s as a
source, t as a terminal), and suppose you were asked to compute a shortest (i.e. cheapest) path between s
and t. Notice that G could possibly have more than one shortest path between s and t. Consider the graph
below for instance: Both P = s, a, t and Q = s, b, t are cheapest paths from s to t.

1 1

s 2 t

1 1

One way to solve this problem is to compute all st paths in G, and choose the cheapest. Notice that if the
graph is unweighted (think of this as all the edges having equal weights), then starting BFS from s would
solve this problem. Maybe we can adjust BFS to take into account the weights.
Recall in BFS vertices are pushed into a queue when visited. When visiting the neighbours of a vertex u,
the ordering in which the neighbours enter the queue is arbitrary. If now the goal is to compute the cheapest
path, then one way to modify BFS would be to push the cheapest neighbours first. By cheapest, we mean
with shortest distance.
“Modified BFS”: Consider using a priority queue instead of a queue to collect unvisited vertices. Set the
priority to be the shortest distance so far. This is precisely the idea behind Dijkstra’s algorithm.
Example: Consider the graph below for instance. Suppose we want to compute the cheapest path from
s = A to t = F .

5 2
B D F
6 11

10
4 C 2 3
3 8

A E G
7 5

The table below keeps track of the distances computed at every iteration from the source A to the every
vertex in the graph. Read the table as follows: In the fist iteration, the distance from the source to itself is
0, and ∞ to any other vertex. At every iteration, choose the cheapest available vertex and try to build the
next cheapest path from said vertex. Repeat the process until all vertices have been visited.

1
2

A B C D E F G Si
i=0 0 ∞ ∞ ∞ ∞ ∞ ∞ ∅
i = 1: A 0 4 3 ∞ 7 ∞ ∞ ∅
i = 2: C 0 4 3 14 7 ∞ ∞ {AC}
i = 3: B 0 4 3 9 7 ∞ ∞ {AC, AB}
i = 4: E 0 4 3 9 7 ∞ 12 {AC, AB, AE}
i = 5: D 0 4 3 9 7 11 12 {AC, AB, AE, BD}
i = 6: F 0 4 3 9 7 11 12 {AC, AB, AE, BD, DF }
i = 7: G 0 4 3 9 7 11 12 {AC, AB, AE, BD, DF, EG}

Notice form the table above that at every iteration i, the set Si is the set of edges that could potentially
lead to a shortest path. If e = (u, v) is added to Si , with u ∈ Si , v ∈
/ Si , then the current value of d[v] is a
shortest sv path. Formally the algorithm is as follows:

Algorithm 1 Dijkstra’s Shortest Path Algorithm

Input: An edge weighted connected graph G(V, E, w) where w : E → R+ and two vertices s, t.
Output: A path from s to t with minimum total cost (shortest path)
1: S = ∅.
2: Initialize empty priority queue.
3: foreach v ∈ V do
4: p[v] = NIL . predecessor of v n shortest s, v path so far
5: d[v] = ∞ . priotity of v = min distance s, v so far.
6: enqueue(v) . With priority d[v] = ∞.
7: end for
8: d[s] = 0
9: Update queue order of s
10: while queue is not empty do . Main Loop
11: v = dequeue element with min priority d[]
12: if p[v]! = NIL then
13: S = S ∪ {(p[v], v)}
14: end if
15: foreach edge (u, v) do
16: if u is in the queue and d[v] + w(v, u) < d[u] then
17: p[u] = v
18: d[u] = d[v] + w(v, u)
19: Update queue order of u
20: end if
21: end for
22: end while
23: return S

Proof of Correctness:
We will argue on the Si ’s. In particular, at every iteration, we generate subsets of edges S1 , S2 , . . . , Sn . We
say that Si can be extended to some collection of shortest paths Si∗ (this is just a tree of shortest paths)
using only edges that do not have both endpoints in Si . That is, we only add edges to Si with at least one
endpoint in the queue.
Loop Invariant
Si is promising, and (1)
∀u ∈ Si , ∀v ∈
/ Si : d[u] = dist[s, v] ≤ dist[s, v] ≤ d[v] (2)
 3

Where dist[s, u] is the minimum cost of all paths from s to u.

Proof. By induction on i.
Base Case: S0 = ∅ is trivially promising.
Induction Hypothesis: For some i, suppose Si can be extended to some shortest paths tree Si ∗, using only
edges without both endpoints in Si , and that:

d[u] = dist[s, u] ≤ dist[s, v] ≤ d[v], for all u ∈ Si , v ∈

/ Si

Induction Step: Consider Si+1 = Si ∪ {(u, v)} with u ∈ Si , v outside Si . We have 2 possible cases:

1. (u, v) ∈ Si∗ :
If (u, v) ∈ Si∗ then Si∗ extends Si+1 and dist[s, v] = dist[s, u] + w(u, v) since (u, v) ∈ Si∗ . Thus we have:

d[v] = d[u] + w(u, v)

= dist[s, u] + w(u, v)
= dist[s, v]

Moreover, since d[v] was the cheapest of all d[·] values for vertices outside Si , it follows that ∀x ∈ Si+1
and ∀y ∈
/ Si+1 : d[x] = d[s, x] ≤ d[s, y] ≤ d[y].
/ Si∗ :
2. (u, v) ∈
Then consider the path P in Si∗ from s to v. P is optimal. Let (z, v) be the last edge on this path.
If z were outside Si , then let (x, y) be the first edge on P with x ∈ Si , y ∈
/ Si (why does such an
edge exist?). We have d[y] ≤ d[x] + w(x, y) (because d[y] is the smallest value of d[t] + w(t, y), ∀e =
(t, y), t ∈ Si .) We thus have:

d[y] ≤ d[x] + w(x, y)

= dist[s, x] + w(x, y)
< dist[s, x] + w(x, y) + dist[y, v] (Since w : E → R+ .)
= dist[s, v]
≤ d[v]
∴ d[y] < d[v]

But this contradicts the fact that d[v] is the smallest d[·] value for all vertices outside Si .
Therefore z must be in Si . This implies that dist[s, v] = dist[s, z] + w(z, v) = d[z] + w(z, v).
Since d[v] is the minimum of all d[x] + w(x, v)∀x ∈ Si , it follows that:

d[v] ≤ d[z] + w(z, v)

= dist[s, v]
∴ d[v] = dist[s, v] (i.e. it is the shortest distance already.)

∗
So we can let Si+1 = Si∗ \{(z, v)} ∪ {(u, v)} and after the update to d[a] for all e = (v, a) with a ∈
/ Si ,
we still have that d[x] = dist[s, x] ≤ dist[s, y] ≤ d[y], for all x ∈ Si , y ∈
/ Si .

Hence the loop invariant holds. When the algorithm terminates, we have: d[u] = dist[s, u], ∀u ∈ V .