Last week recap
• Greedy algorithms:
ØInterval Scheduling
ØInterval Partioning
ØMinimum Lateness Scheduling ØHuffman Code
2021-01-25 CSC373 Winter 2021 – Sam Toueg 1
Greedy Algorithms Dijkstra’s Algorithm
2021-01-25 CSC373 Winter 2021 – Sam Toueg 2
Single-Source Shortest Path
• Problem
ØInput: •
• Each edge 𝑢, 𝑣 has a non-negative weight (“length’’) 𝑤!”
• Source node 𝑠 ∈ 𝑉
Directed graph 𝐺 = 𝑉, 𝐸
ØOutput: length of shortest path from 𝑠 to each node 𝑡 ∈ 𝑉
𝑠2𝑣 lengthoftheshortestpathfrom𝑠to𝑢=7 (path𝑠→𝑣→𝑢)
5 10
𝑢
2021-01-25
CSC373 Winter 2021 – Sam Toueg 3
Single-Source Shortest Path
• Problem
ØInput: •
• Each edge 𝑢, 𝑣 has a non-negative weight (“length’’) 𝑤!”
• Source node 𝑠 ∈ 𝑉
Directed graph 𝐺 = 𝑉, 𝐸
ØOutput: length of shortest path from 𝑠 to each node 𝑡 ∈ 𝑉
• Let 𝑅 be a subset of nodes of 𝐺 that includes source 𝑠
• Apath𝑠⤳𝑣isan𝑅-path𝑠⤳𝑣ifitcontainsonlynodesin𝑅
(except possibly for 𝑣) 𝑠→→………→𝑣
∈𝑅
𝑅-path 𝑠 ⤳ 𝑣
2021-01-25 CSC373 Winter 2021 – Sam Toueg 4
Dijkstra’s Algorithm
• The algorithm maintains a set of nodes 𝑅 ⊆ 𝑉 and for each node 𝑣 a value 𝑑 𝑣 , such that: 1. ∀𝑣∈ 𝑅: 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣path
2. ∀𝑣∈𝑉−𝑅∶ 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣𝑅-path
• In each iteration, the algorithm adds one more node to 𝑅 and maintains (1) and (2) How?
length of shortest 𝑠 ⤳ 𝑣 path
𝑑𝑣
𝑣 𝑠
𝑅
length of shortest 𝑠 ⤳ 𝑣′ 𝑅-path
𝑉−𝑅
𝑑 𝑣′ 𝑣′
2021-01-25
CSC373 Winter 2021 – Sam Toueg 5
Dijkstra’s Algorithm
• The algorithm maintains a set of nodes 𝑅 ⊆ 𝑉 and for each node 𝑣 a value 𝑑 𝑣 , such that: 1. ∀𝑣∈ 𝑅: 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣path
2. ∀𝑣∈𝑉−𝑅∶ 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣𝑅-path
• In each iteration, the algorithm adds one more node to 𝑅 and maintains (1) and (2) How?
𝑣
𝑠𝑢 𝑤
𝑅
𝑉−𝑅
2021-01-25
CSC373 Winter 2021 – Sam Toueg 6
Dijkstra’s Algorithm
• The algorithm maintains a set of nodes 𝑅 ⊆ 𝑉 and for each node 𝑣 a value 𝑑 𝑣 , such that: 1. ∀𝑣∈ 𝑅: 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣path
2. ∀𝑣∈𝑉−𝑅∶ 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣𝑅-path
• In each iteration, the algorithm adds one more node to 𝑅 and maintains (1) and (2) How?
shortest 𝑅−paths
𝑣𝑑𝑣
𝑠 𝑢𝑑𝑢 𝑤𝑑𝑤
𝑅
𝑉−𝑅
2021-01-25
CSC373 Winter 2021 – Sam Toueg 7
Dijkstra’s Algorithm
• The algorithm maintains a set of nodes 𝑅 ⊆ 𝑉 and for each node 𝑣 a value 𝑑 𝑣 , such that: 1. ∀𝑣∈ 𝑅: 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣path
2. ∀𝑣∈𝑉−𝑅∶ 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣𝑅-path
• In each iteration, the algorithm adds one more node to 𝑅 and maintains (1) and (2) How?
shortest 𝑅−paths
Let 𝑢 : node with min 𝑑-value in 𝑉 − 𝑅
We know: 𝑑(𝑢) = length of shortest 𝑠 ⤳ 𝑢 𝑅-path
We claim: 𝑑(𝑢) = length of shortest 𝑠 ⤳ 𝑢 𝑅-path
If this claim holds then we can:
a) move 𝑢 from 𝑉 − 𝑅 to 𝑅 and still maintain (1), then b) update the 𝑑() of nodes in 𝑉 − 𝑅 to satisfy (2)
𝑉−𝑅
𝑣𝑑𝑣
𝑠 𝑢𝑑𝑢 𝑤𝑑𝑤
𝑅
2021-01-25
CSC373 Winter 2021 – Sam Toueg 8
Dijkstra’s Algorithm
• The algorithm maintains a set of nodes 𝑅 ⊆ 𝑉 and for each node 𝑣 a value 𝑑 𝑣 , such that: 1. ∀𝑣∈ 𝑅: 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣path
2. ∀𝑣∈𝑉−𝑅∶ 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣𝑅-path
• In each iteration, the algorithm adds one more node to 𝑅 and maintains (1) and (2) How?
Let 𝑢 : node with min 𝑑-value in 𝑉 − 𝑅
We know: 𝑑(𝑢) = length of shortest 𝑠 ⤳ 𝑢 𝑅-path
We claim: 𝑑(𝑢) = length of shortest 𝑠 ⤳ 𝑢 𝑅-path
If this claim holds then we can:
a) move 𝑢 to 𝑅 and still maintain (1)
b) update the 𝑑() of nodes in 𝑉 − 𝑅 to satisfy (2)
𝑉−𝑅
𝑣𝑑𝑣 𝑑𝑢
𝑠𝑢
𝑤𝑑𝑤
𝑅
2021-01-25
CSC373 Winter 2021 – Sam Toueg 9
• •
Dijkstra’s Algorithm
The algorithm maintains a set of nodes 𝑅 ⊆ 𝑉 and for each node 𝑣 a value 𝑑 𝑣 , such that: 1. ∀𝑣∈ 𝑅: 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣path
2. ∀𝑣∈𝑉−𝑅∶ 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣𝑅-path
In each iteration, the algorithm adds one more node to 𝑅 and maintains (1) and (2) How? Let 𝑢 : node with min 𝑑-value in 𝑉 − 𝑅 We know: 𝑑(𝑢) = length of shortest 𝑠 ⤳ 𝑢 𝑅-path
𝑃 ” 𝑃!
𝑠
𝑅
We claim: 𝑑(𝑢) = length of shortest 𝑠 ⤳ 𝑢 𝑅-path
Proof Sketch: By contra. Let 𝑃 be a shorter 𝑠 ⤳ 𝑢 path: l 𝑃 < 𝑑(𝑢) Let 𝑣 be the first node of path 𝑃 in 𝑉 − 𝑅
𝑃
𝑣 𝑑 𝑣
𝑢 𝑑 𝑢 𝑤𝑑𝑤
𝑉−𝑅
So𝑃=𝑃" 𝑃! asshown. Notethat𝑃" isan𝑠⤳𝑣𝑅-path
l 𝑃 = l 𝑃" + l 𝑃!
l 𝑃 ≥l 𝑃" ≥ 𝑑 𝑣
Bcs:l 𝑃! ≥0 (edgeweightsarenon-negative!) Bcs: 𝑑(𝑣) = length of shortest 𝑠 ⤳ 𝑣 𝑅-path
Bcs:𝑢isnodewithmin𝑑−valuein𝑉−𝑅 Contradiction!
≥𝑑 𝑢
2021-01-25
CSC373 Winter 2021 - Sam Toueg 10
• •
Dijkstra’s Algorithm
The algorithm maintains a set of nodes 𝑅 ⊆ 𝑉 and for each node 𝑣 a value 𝑑 𝑣 , such that: 1. ∀𝑣∈ 𝑅: 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣path
2. ∀𝑣∈𝑉−𝑅∶ 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣𝑅-path
In each iteration, the algorithm adds one more node to 𝑅 and maintains (1) and (2) How? Let 𝑢 : node with min 𝑑-value in 𝑉 − 𝑅 We proved: 𝑑(𝑢) = length of shortest 𝑠 ⤳ 𝑢 path
So we can move 𝑢 to set 𝑅, without changing its 𝑑(𝑢), and this still satisfies (1)
𝑣𝑑𝑣
𝑠 𝑢𝑑𝑢 𝑤𝑑𝑤
𝑅
𝑉−𝑅
2021-01-25
CSC373 Winter 2021 - Sam Toueg 11
• •
Dijkstra’s Algorithm
The algorithm maintains a set of nodes 𝑅 ⊆ 𝑉 and for each node 𝑣 a value 𝑑 𝑣 , such that: 1. ∀𝑣∈ 𝑅: 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣path
2. ∀𝑣∈𝑉−𝑅∶ 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣𝑅-path
In each iteration, the algorithm adds one more node to 𝑅 and maintains (1) and (2) How? Let 𝑢 : node with min 𝑑-value in 𝑉 − 𝑅 We proved: 𝑑(𝑢) = length of shortest 𝑠 ⤳ 𝑢 path
So we can move 𝑢 to set 𝑅, without changing its 𝑑(𝑢), and this still satisfies (1)
𝑣𝑑𝑣 𝑑𝑢
𝑠𝑢
𝑤𝑑𝑤
𝑅
𝑉−𝑅
2021-01-25
CSC373 Winter 2021 - Sam Toueg 12
• •
Dijkstra’s Algorithm
The algorithm maintains a set of nodes 𝑅 ⊆ 𝑉 and for each node 𝑣 a value 𝑑 𝑣 , such that: 1. ∀𝑣∈ 𝑅: 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣path
2. ∀𝑣∈𝑉−𝑅∶ 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣𝑅-path
In each iteration, the algorithm adds one more node to 𝑅 and maintains (1) and (2) How? Let 𝑢 : node with min 𝑑-value in 𝑉 − 𝑅 We proved: 𝑑(𝑢) = length of shortest 𝑠 ⤳ 𝑢 path
Butnowthat𝑅alsocontainsnode𝑢: wemustupdatethe𝑑 𝑣 ofeach𝑣in𝑉−𝑅 How? to ensure that (2) still holds
𝑃"
Observation: there are two possible cases.
• shortest 𝑠 ⤳ 𝑣 𝑅-path does not contain 𝑢
Ø In this case 𝑑 𝑣 is unchanged
• shortest 𝑠 ⤳ 𝑣 𝑅-path contains 𝑢
ØInthiscasenew𝑑 𝑣 =𝑑 𝑢 +𝑤#$ Soforevery𝑣in𝑉−𝑅update𝑑 𝑣 asfollows:
𝑣𝑑𝑣 𝑑𝑢
𝑃!
𝑠𝑢
𝑅
2021-01-25
𝑉−𝑅
𝑑𝑣 =min(𝑑𝑣,𝑑𝑢 +𝑤#$)
CSC373 Winter 2021 - Sam Toueg 13
𝑤!"
• •
Dijkstra’s Algorithm
The algorithm maintains a set of nodes 𝑅 ⊆ 𝑉 and for each node 𝑣 a value 𝑑 𝑣 , such that: 1. ∀𝑣∈ 𝑅: 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣path
2. ∀𝑣∈𝑉−𝑅∶ 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣𝑅-path
In each iteration, the algorithm adds one more node to 𝑅 and maintains (1) and (2) How? Let 𝑢 : node with min 𝑑-value in 𝑉 − 𝑅 We proved: 𝑑(𝑢) = length of shortest 𝑠 ⤳ 𝑢 path
Butnowthat𝑅alsocontainsnode𝑢: wemustupdatethe𝑑 𝑣 ofeach𝑣in𝑉−𝑅 How? to ensure that (2) still holds
Why can’t the shortest 𝑠 ⤳ 𝑣 𝑅-path be 𝑃# ?
𝑃"
Observation: there are two possible cases.
• shortest 𝑠 ⤳ 𝑣 𝑅-path does not contain 𝑢
Ø In this case 𝑑 𝑣 is unchanged
• shortest 𝑠 ⤳ 𝑣 𝑅-path contains 𝑢
ØInthiscasenew𝑑 𝑣 =𝑑 𝑢 +𝑤#$ WHY? Soforevery𝑣in𝑉−𝑅update𝑑 𝑣 asfollows:
𝑣𝑑𝑣 𝑑𝑢
𝑠𝑢
𝑃%
𝑃!
𝑟 𝑅
2021-01-25
𝑉−𝑅
𝑑𝑣 =min(𝑑𝑣,𝑑𝑢 +𝑤#$)
CSC373 Winter 2021 - Sam Toueg 16
𝑤!"
• •
Dijkstra’s Algorithm
The algorithm maintains a set of nodes 𝑅 ⊆ 𝑉 and for each node 𝑣 a value 𝑑 𝑣 , such that: 1. ∀𝑣∈ 𝑅: 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣path
2. ∀𝑣∈𝑉−𝑅∶ 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣𝑅-path
In each iteration, the algorithm adds one more node to 𝑅 and maintains (1) and (2) How? Let 𝑢 : node with min 𝑑-value in 𝑉 − 𝑅 We proved: 𝑑(𝑢) = length of shortest 𝑠 ⤳ 𝑢 path
Butnowthat𝑅alsocontainsnode𝑢: wemustupdatethe𝑑 𝑣 ofeach𝑣in𝑉−𝑅 How? to ensure that (2) still holds
Because shortest path to 𝑟 does not contain 𝑢! Observation: there are two possible cases.
𝑃"
• shortest 𝑠 ⤳ 𝑣 𝑅-path does not contain 𝑢 Ø In this case 𝑑 𝑣 is unchanged
• shortest 𝑠 ⤳ 𝑣 𝑅-path contains 𝑢 ØInthiscasenew𝑑 𝑣 =𝑑 𝑢 +𝑤#$ WHY?
Soforevery𝑣in𝑉−𝑅update𝑑 𝑣 asfollows: 𝑑𝑣 =min(𝑑𝑣,𝑑𝑢 +𝑤#$)
𝑣𝑑𝑣 𝑑𝑢
𝑠𝑢
𝑃%
𝑃!
𝑟 𝑅
𝑉−𝑅
2021-01-25
CSC373 Winter 2021 - Sam Toueg 17
𝑤!"
• •
Dijkstra’s Algorithm
The algorithm maintains a set of nodes 𝑅 ⊆ 𝑉 and for each node 𝑣 a value 𝑑 𝑣 , such that: 1. ∀𝑣∈ 𝑅: 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣path
2. ∀𝑣∈𝑉−𝑅∶ 𝑑 𝑣 =lengthofshortest𝑠⤳𝑣𝑅-path
In each iteration, the algorithm adds one more node to 𝑅 and maintains (1) and (2) How? Let 𝑢 : node with min 𝑑-value in 𝑉 − 𝑅 We proved: 𝑑(𝑢) = length of shortest 𝑠 ⤳ 𝑢 path
Butnowthat𝑅alsocontainsnode𝑢: wemustupdatethe𝑑 𝑣 ofeach𝑣in𝑉−𝑅 How? to ensure that (2) still holds
𝑣𝑑𝑣 𝑑𝑢
𝑠𝑢
𝑤𝑑𝑤
Observation: there are two possible cases.
• shortest 𝑠 ⤳ 𝑣 𝑅-path does not contain 𝑢
Ø In this case 𝑑 𝑣 is unchanged
• shortest 𝑠 ⤳ 𝑣 𝑅-path contains 𝑢
ØInthiscasenew𝑑 𝑣 =𝑑 𝑢 +𝑤#$ Soforevery𝑣in𝑉−𝑅update𝑑 𝑣 asfollows:
𝑅
2021-01-25
𝑉−𝑅
𝑑𝑣 =min(𝑑𝑣,𝑑𝑢 +𝑤#$)
CSC373 Winter 2021 - Sam Toueg 18
𝑤!"
𝑤!$
Dijkstra’s Algorithm
𝑅 ← {𝑠} 𝑑(𝑠) ← 0
foreachnode𝑣≠𝑠doif(𝑠,𝑣)isanedgethen𝑑(𝑣)←𝑤!" else𝑑(𝑣)←∞ while 𝑅 ≠ 𝑉 do
𝑢 ← node not in 𝑅 with minimum 𝑑-value 𝑅 ← 𝑅 ∪ {𝑢}
for each node 𝑣 s.t. (𝑢, 𝑣) is an edge do
𝑠 𝑑 𝑠 =0
𝑅
if 𝑑 𝑣 > 𝑑 𝑢 + 𝑤#$ then 𝑑 𝑣 ← 𝑑 𝑢 + 𝑤#”
𝑣𝑑𝑣
𝑢 𝑑 𝑢 𝑤𝑑𝑤
𝑉−𝑅
2021-01-25
CSC373 Winter 2021 – Sam Toueg 19
𝑢 : node in 𝑉 − 𝑅 with minimum 𝑑-value
Dijkstra’s Algorithm
𝑅 ← {𝑠} 𝑑(𝑠) ← 0
𝑝(𝑣) ← 𝑠 𝑝(𝑣) ← 𝑁𝑖𝑙
foreachnode𝑣≠𝑠doif(𝑠,𝑣)isanedgethen𝑑(𝑣)←𝑤!” else𝑑(𝑣)←∞ while 𝑅 ≠ 𝑉 do
𝑢 ← node not in 𝑅 with minimum 𝑑-value 𝑅 ← 𝑅 ∪ {𝑢}
for each node 𝑣 s.t. (𝑢, 𝑣) is an edge do
if 𝑑 𝑢 + 𝑤#” < 𝑑 𝑣 then 𝑑 𝑣 ← 𝑑 𝑢 + 𝑤#"
𝑝(𝑣) ← 𝑢
𝑣𝑑𝑣 𝑑𝑢
𝑠𝑢𝑢𝑑𝑢 𝑤𝑑𝑤
𝑅
can compute the shortest paths by maintaining 𝑝(𝑣): predecessor of 𝑣 on 𝑠 ⤳ 𝑣 path
𝑉−𝑅
2021-01-25
CSC373 Winter 2021 - Sam Toueg 20
𝑤!"
𝑤!$
Dijkstra’s Algorithm
𝑅 ← {𝑠} 𝑑(𝑠) ← 0
foreachnode𝑣≠𝑠doif(𝑠,𝑣)isanedgethen𝑑(𝑣)←𝑤!" else𝑑(𝑣)←∞ while 𝑅 ≠ 𝑉 do
𝑢 ← node not in 𝑅 with minimum 𝑑-value 𝑅 ← 𝑅 ∪ {𝑢}
for each node 𝑣 s.t. (𝑢, 𝑣) is an edge do
if 𝑑 𝑢 + 𝑤#" < 𝑑 𝑣 then 𝑑 𝑣 ← 𝑑 𝑢 + 𝑤#"
Dijkstra’s Algorithm does not work with negative weights!
3B
S -2 A 2C1
S⤳A: 2+1
Path found by the algorithm: S → C → A Length 3
ShortestPath: S→B→C→A Length 2 3 + -2 + 1
2021-01-25
CSC373 Winter 2021 - Sam Toueg
21
Dijkstra’s Algorithm
𝑅 ← {𝑠} 𝑑(𝑠) ← 0
foreachnode𝑣≠𝑠doif(𝑠,𝑣)isanedgethen𝑑(𝑣)←𝑤!" else𝑑(𝑣)←∞ 𝑂(𝑛) while 𝑅 ≠ 𝑉 do 𝑛 iterations
𝑢 ← node not in 𝑅 with minimum 𝑑-value
𝑅 ← 𝑅 ∪ {𝑢}
for each node 𝑣 s.t. (𝑢, 𝑣) is an edge do 𝑂(𝑚) in total
if 𝑑 𝑢 + 𝑤#" < 𝑑 𝑣 then 𝑑 𝑣 ← 𝑑 𝑢 + 𝑤#"
𝑂(𝑛)
Worst-case running time for a graph with 𝑛 nodes and 𝑚 edges Naïve implementation: 𝑂 𝑛! + 𝑚 = 𝑂(𝑛!)
2021-01-25 CSC373 Winter 2021 - Sam Toueg 23
Dijkstra’s Algorithm Idea: keep nodes that are not in 𝑅 in a min-heap
𝑅 ← {𝑠} with their 𝑑-value as keys 𝑑(𝑠) ← 0
foreachnode𝑣≠𝑠doif(𝑠,𝑣)isanedgethen𝑑(𝑣)←𝑤!" else𝑑(𝑣)←∞ 𝑂(𝑛) while 𝑅 ≠ 𝑉 do 𝑛 iterations
𝑅 ← 𝑅 ∪ {𝑢}
for each node 𝑣 s.t. (𝑢, 𝑣) is an edge do
if 𝑑 𝑢 + 𝑤#" < 𝑑 𝑣 then 𝑑 𝑣 ← 𝑑 𝑢 + 𝑤#"
𝑢 ← node not in 𝑅 with minimum 𝑑-value
𝑂(𝑛) 𝑂(𝑚) in total
expensive
Worst-case running time for a graph with 𝑛 nodes and 𝑚 edges Naïve implementation: 𝑂 𝑛! + 𝑚 = 𝑂(𝑛!)
2021-01-25 CSC373 Winter 2021 - Sam Toueg 24
Dijkstra’s Algorithm
𝑅 ← {𝑠} 𝑑(𝑠) ← 0
foreachnode𝑣≠𝑠doif(𝑠,𝑣)isanedgethen𝑑(𝑣)←𝑤!" else𝑑(𝑣)←∞ 𝑂(𝑛) 𝑁𝑅 ← min heap of all the nodes 𝑣 ≠ 𝑠 with their 𝑑-value as keys 𝑂(𝑛)
while 𝑅 ≠ 𝑉 do 𝑛 iterations 𝑢 ← 𝑁𝑅. ExtractMin()
𝑅 ← 𝑅 ∪ {𝑢}
for each node 𝑣 s.t. (𝑢, 𝑣) is an edge do
if 𝑑 𝑢 + 𝑤#" < 𝑑 𝑣 then 𝑑 𝑣 ← 𝑑 𝑢 + 𝑤#"
𝑂(log 𝑛)
𝑁𝑅. ChangeKey(𝑣, 𝑑(𝑣))
𝑂(𝑚𝑙𝑜𝑔𝑛) in total
Sophisticated implementation: 𝑂 𝑛 + 𝑛𝑙𝑜𝑔𝑛 + 𝑚𝑙𝑜𝑔𝑛 = 𝑂( 𝑛 + 𝑚 𝑙𝑜𝑔𝑛)
If we assume that there is a path from 𝑠 to every node, then 𝑚 ≥ 𝑛 − 1 In this case, the time complexity is 𝑂 𝑚𝑙𝑜𝑔𝑛
2021-01-25 CSC373 Winter 2021 - Sam Toueg 27
Dijkstra’s Algorithm
Implementation
Time Complexity
sparse graphs
𝑚 ≈ 𝑂(𝑛)
Sophisticated
Θ( 𝑛+𝑚 𝑙𝑜𝑔𝑛)
✅
Naïve
Θ(𝑛%)
2021-01-25 CSC373 Winter 2021 - Sam Toueg 28
Dijkstra’s Algorithm
Implementation
Time Complexity
sparse graphs, e.g., 𝑚 ≈ Θ(𝑛) or
𝑚 ≈ Θ(𝑛𝑙𝑜𝑔𝑛)
Sophisticated
Θ( 𝑛+𝑚 𝑙𝑜𝑔𝑛)
✅
Naïve
Θ(𝑛%)
2021-01-25 CSC373 Winter 2021 - Sam Toueg 29
Dijkstra’s Algorithm
Implementation
Time Complexity
sparse graphs, e.g., 𝑚 ≈ Θ(𝑛) or
𝑚 ≈ Θ(𝑛𝑙𝑜𝑔𝑛)
dense graphs
𝑚 ≈ Θ(𝑛%)
Sophisticated
Θ( 𝑛+𝑚 𝑙𝑜𝑔𝑛)
✅
Naïve
Θ(𝑛%)
✅
2021-01-25 CSC373 Winter 2021 - Sam Toueg 30