6CCS3OME/7CCSMOME – Optimisation Methods
Lecture 2
Single-source shortest-paths: Dijkstra’s algorithm, shortest-paths algorithm for DAGs
Tomasz Radzik and Kathleen Steinho ̈fel
Department of Informatics, King’s College London 2020/21, Second term
Topics
• Single-source shortest-paths; restricted cases • Only non-negative edge weights allowed:
Dijkstra’s shortest-paths algorithm
• The input graph is acyclic (a DAG – a directed acyclic graph): Single-source shortest paths algorithm for DAG’s
• In both cases, the Bellman-Ford shortest-paths algorithm can be used.
In both cases, the new algorithms are faster than the Bellman-Ford algorithm.
6CCS3OME/7CCSMOME, Lecture 2
2 / 27
8 8
Dijkstra’s shortest-paths algorithm
• Crucial assumption: all edge weights are nonnegative.
• For convenience, assume that all nodes are reachable from s.
node a b c h r s v x y z
DIJKSTRA(G, w, s) INITIALIZATION(G, s) S ← ∅
Q ← V
d∞∞∞∞∞0∞∞∞∞
while Q̸=∅ do
u ← EXTRACT-MIN(Q)
{ u has the min d[.] value in Q } for each node v ∈ Adj[u] do RELAX(u,v,w)
0 s
S ← S ∪ {u} end while .
3
• Q is implemented as a
Priority Queue data structure.
Priority Queue maintains pairs (value, key) and the main operation is EXTRACT-MIN.
12
u
6
In Dijkstra’s algorithm: pairs (node, d[node]). 6CCS3OME/7CCSMOME, Lecture 2
3 / 27
PARENT nil nil nil nil nil nil nil nil nil nil
{ G = (V, E) }
{ “relaxation technique” initialization }
{ nodes v for which we know that d[v] = δ(s, v) } { the other nodes in Priority Queue with keys d[.]}
S
5
9 14
15
15
11 Q
7
7
2
Example
From [CLRS] textbook:
s
5
7
6CCS3OME/7CCSMOME, Lecture 2
4 / 27
10
23
9
46
u
1
v
xy 2
8
8
8
8
8
8
8
8
Example: initialization (continued at LGT)
From [CLRS] textbook:
0
23
9
46
s
5
7
u 10
1
v
Q = { (s,0), (u, ), (v,
), (x,
), (y,
) }
6CCS3OME/7CCSMOME, Lecture 2
5 / 27
xy 2
8
8
The correctness of Dijkstra’s algorithm
An intermediate state of the computation (at the end of one iteration).
• Set S grows by one node per one iteration
set S
End 1-st iter.: S = {s} End last iter.: S = V
s
• All edges from nodes in S, and only these edges, have been relax’ed.
• AllnodesinS orattheendofedgesfromS:
• have finite d[.] values (by induction)
• have parents, forming a tree (no negative cycles and Prop. (8)). • For all other nodes, d[.] = ∞, and not in the parent tree.
6CCS3OME/7CCSMOME, Lecture 2
6 / 27
d[.] finite
The correctness of Dijkstra’s algorithm (2)
At the end of set S = V the computation:
• SetS=V.
For each v ∈ V , d[v] is finite and d[v] ≥ δ(s, v). The parent subgraph is a tree (rooted at s) which includes all nodes.
• We haven’t shown yet that the computed: tree is a shortest paths tree and
the d[.] values are the shortest-path weights.
6CCS3OME/7CCSMOME, Lecture 2
7 / 27
all d[.] finite
s
8 8
8 8
8
8
8 8
8
8
8
The correctness of Dijkstra’s algorithm (2): the crucial property
The crucial property (the invariant of the computation of Dijkstra’s algorithm):
At the end of each iteration (on the main loop) of Dijkstra’s algorithm, foreachnodev∈S, d[v]=δ(s,v).
• This property can be shown by induction on the number of iterations.
• Basis of the induction: The property holds at the end of the first iteration:
S={s}, d[s]=0=δ(s,s). set S
6
6CCS3OME/7CCSMOME, Lecture 2
8 / 27
5
6 5
s 2
5 2
0
5
8
8
8
8
8
8
8
8
8
8
8
8
8
8
The invariant of Dijkstra’s algorithm: the induction step
Induction step:
set S
• Assume the invariant holds at the end of some iteration
(not the last one):
s
for each v ∈ S, d[v] = δ(s, v).
• Let u denote the node selected in the next (current) iteration.
set S
u
• Show that the invariant holds at the end of
the current iteration, (after u added to set S).
s
• That is, show that d[u] = δ(s, u).
6CCS3OME/7CCSMOME, Lecture 2
9 / 27
u
The invariant of Dijkstra’s algorithm: the induction step (cont.)
• We have to show that at the beginning of the current iteration, d[u] is the shortest-path weight from s to u. That is, we have to show that d[u] = δ(s, u).
• We have d[u] ≥ δ(s, u) (relaxation technique). We show d[u] ≤ δ(s, u).
set S the tree path to x
u x
• Take any (simple) path R from s to u and show that its weight w(R) ≥ d[u].
R2
• Letzbethefirstnodeon path R which is outside S, and let y be the predecessor of z on R (so y ∈ S).
s
R1 y
z
x = Parent[u]
• Let R1 be the initial part of path R ending at node y, and let R2 be the part of path R from node z to the final node u.
• w(R) = w(R1)+w(y,z)+w(R2) ≥ d[y]+w(y,z)+w(R2) ≥ d[z]+w(R2) ≥ d[u]+w(R2) ≥ d[u].
• The inequalities above follow from: the inductive assumption, RELAX(y,z) done, the rule for selecting u, and the non-negative weights of edges, respectively.
• Thus no path from s to u has smaller weight than d[u], so d[u] ≤ δ(s, u). 6CCS3OME/7CCSMOME, Lecture 2
10 / 27
The running time of Dijkstra’s algorithm
• n – number of nodes; m – number of edges.
• Initialisation (as in the relaxation technique): Θ(n).
• For every edge (u, v), RELAX(u, v) is performed exactly once.
This happens during the iteration when node u is removed from Q. (Each node is removed from Q exactly once.)
• The running time depends on the implementation of the priority queue Q.
• Notethat n−1≤m≤n(n−1), so m=Ω(n) and m=O(n2).
• The naive implementation of Q, using an unordered list of elements: bcfklpqrsw
Q:w c b k q d:
• one EXTRACT-MIN(Q): O(n) time; all of them: O(n2); • one RELAX operation: O(1); all of them: O(m);
• the total running time: Θ(n) + O(n2) + O(m) = O(n2).
• What would be the running time of Dijkstra’s algorithm, if Q was maintained
asanorderedlist? (LGT).
6CCS3OME/7CCSMOME, Lecture 2 11 / 27
PriorityQueueimplementedasHeap: operationsandperformance
• To improve the running time of Dijkstra’s algorithm, use the Heap implementation of the Priority-Queue to maintain Q.
• The main Priority Queue operations in Heap (n denotes the size of the heap, that is, the number of elements in the heap):
• INSERT(Q, v, k): insert the value-key pair (v, k). O(log n) time
• EXTRACT-MIN(Q): remove and return the pair with the smallest key.
• Check if Heap is not empty.
• Initialise Heap with given n elements.
O(log n) time O(1) (constant) time Θ(n) time.
• In Dijkstra’s algorithm, we also need heap operation: HEAP-DECREASE-KEY(Q, v, k)
– decrease the key associated with v to k. O(log n) time
6CCS3OME/7CCSMOME, Lecture 2
12 / 27
Dijkstra’s algorithm with Heap
• The set Q in Dijkstra’s algorithm maintained as Heap:
• Initialisation of the Heap: Θ(n) time.
• One EXTRACT-MIN(Q): O(log n) time; all: O(n log n) time.
• one RELAX(u, v): O(log n) time, since it may involve one operation HEAP-DECREASE-KEY; all: O(m log n) time.
• The total running time of Dijkstra’s algorithm with Heap is: Θ(n)+Θ(n)+O(nlogn)+O(mlogn)=O(mlogn).
• If the input graph is dense, that is (here), if m = Ω(n2/ log n), then the implementation of Dijkstra’s algorithm without Heap (maintaining Q as an unordered list) gives the better (worst-case) running time – O(n2).
• For the other cases (when m = O(n2/ log n)), the implementation of Dijkstra’s algorithm with Heap gives the better (worst-case) running time.
• In most applications of Dijkstra’s algorithm, graphs are not dense, so Dijkstra’s algorithm is commonly assumed to use Heap.
6CCS3OME/7CCSMOME, Lecture 2
13 / 27
Heap implementation of Priority Queue data structure
• Heap: An array A[1..n] with a sequence of numbers (keys) and associated data (values), satisfying some specific partial order of the entries.
This specific order is called the heap property (Min-Heap here):
A[i]≤A[2i] and A[i]≤A[2i+1], fori=1,2,… Below, an arrow points from a smaller key to a larger key:
A[1] A[2] A[3] A[4] A[5]A[6]
A[i]
A[2i]A[2i+1]
smallest key
A[4] A[5]
A[6] A[7]
A[2]
A[3]
A[1]
• The operations of extracting the minimum and inserting a new element take O(log n) time, where n is the current size of the Heap.
6CCS3OME/7CCSMOME, Lecture 2 14 / 27
A[2i]
A[2i+1]
A[i]
Heap in Dijkstra’s algorithm
The entries in the Heap array are the pairs (u, d[u]), where u is a node in the graph and d[u] is its current shortest path estimate. The number d[u] is the key of this entry.
Q_A:
4
………………………
x
y z
pos_in_Q:
………………………
1 2 3
x y z v
d[x] d[y] d[z] d[v]
………………………
y 2413
vxz
v
• We need a heap operation HEAP-DECREASE-KEY, which restores the heap property when the key of one entry is decreased.
RELAX(u,v) (in Dijkstra’s algorithm, if Q is a Heap) if d[v]>d[u]+w(u,v) then
d[v] ← d[u] + w(u, v); PARENT[v] ← u HEAP-DECREASE-KEY(Q, v, d[v])
Operation HEAP-DECREASE-KEY takes O(log n) time.
6CCS3OME/7CCSMOME, Lecture 2 15 / 27
Heap Extract-Min operation
6CCS3OME/7CCSMOME, Lecture 2
16 / 27
log (n) 2
min
Heap-Decrease-Key operation
6CCS3OME/7CCSMOME, Lecture 2
17 / 27
log (n) 2
pos_in_Q:
v
v
Single-source shortest paths in DAG’s
Input:
• G = (V, E) – directed acyclic graph (DAG);
• w – weights of edges (may be negative);
• s∈V – thesourcenode.
3 a −1 b 8
Output: theshortest-pathweightsfromstoallothernodes and a shortest-paths tree from s.
There may be edges with negative weights, but no problem with negative cycles, because there are no cycles at all.
Bellman-Ford: O(mn).
We show an algorithm which runs in O(n + m) time.
(Linear, optimal time) 6CCS3OME/7CCSMOME, Lecture 2
18 / 27
s
4 −2
1 3
c
d
5 e
Application
• Determine the critical (longest) paths in PERT chart analysis (Program Evaluation and Review Technique).
• Nodes: milestones of the project (‘synchronisation points’) . Edges: tasks of the project. The weight of an edge: the duration of this task.
Find the longest path from node “begin” to node “end”:
this gives the fastest possible time for completing the whole project (that is, for completing all tasks of the project).
begin
3
a
4g
3
end
6CCS3OME/7CCSMOME, Lecture 2
19 / 27
e
5
5
15
3 h
1
3
b 46
3
c
4 p6 23
4
f
d2
7
q
3
17
DAGs: Longest paths to shortest paths by negating all egde weights
• To compute longest paths from the start node, negate all edge weights and compute shortest paths from the start node.
begin
a
end
6CCS3OME/7CCSMOME, Lecture 2
20 / 27
−1
−1
−4
−3 −3f c
b
−4 −5 −6
−4 −3−3 p−6−23
−4g −3 −5
−17
e −5
h
−3
d −2
−7
q
Algorithm
• Consider the nodes in a topological order: all edges go in the same direction.
begin
1: 2: 3: 4: 5:
topologically sort the nodes of G { put the nodes in a topological order } INITIALIZATION(G,s)
for
each node u taken in the topological order computed in step 1 for each node v ∈ Adj[u] do
do
aegbchdf
p q end
DAGSHORTESTPATHS(G, w, s)
RELAX(u, v, w) • Runningtime: O(n+m)
(topological sort takes O(n + m) time).
• Correctness: show (by induction) that when
node u is considered in line 3, then d[u] = δ(s, u). 6CCS3OME/7CCSMOME, Lecture 2
21 / 27
Examples and Exercises – LGT
1. Example of the computation of Dijkstra’s algorithm – slides 4-5.
2. What would be the running time of Dijkstra’s algorithm, if the priority queue
Q was maintained as an ordered list?
6CCS3OME/7CCSMOME, Lecture 2 22 / 27
Examples and Exercises – LGT (cont)
3. (Exercise 24.2-3 from [CLRS])
The PERT chart formulation given in this lecture is somewhat unnatural. More naturally, vertices would represent tasks and edges would represent order constraints; edge (u, v) would indicate that task u must be performed before task v. We would then assign weights (duration of the tasks) to vertices, not edges. Modify the DAGSHORTESTPATHS algorithm so that it finds, in linear time, a longest path in a directed acyclic graph with weighted vertices. Let w(v) denote the weight of a vertex v.
Trace the computation of the algorithm on the graph below.
The green path has weight 20.
b3f c
26
The red path,
with weight 26,
is the longest path.
g
6CCS3OME/7CCSMOME, Lecture 2
23 / 27
4 3
4 3
begin a
p end
5 4d6
e
h 7q2
1
2
20
Exercises – SGT
1. This exercise shows that Dijkstra’s algorithm does not necessary compute shortest paths, if there are negative weights; even if there are no negative cycles.
(a) Show the values d[x] and the tree computed by Dijkstra’s algorithm for the input graph:
a
(b) Show the shortest-path weights and a shortest-paths tree in this graph.
(c) How to modify Dijkstra’s algorithm so that it runs also for graphs where edge weights may be negative?
(d) What is the running time of the modified algorithm?
6CCS3OME/7CCSMOME, Lecture 2
24 / 27
8 s
6 b
d
4
8 -6
7
4
4 c
Exercises – SGT (cont.)
2. Design a linear-time (O(n + m)-time) algorithm which for a given directed acyclic graph (with n nodes and m edges) computes a topological order of the nodes.
Do not use the Depth-First Search (DFS) algorithm.
(There is a topological sort algorithm which is based on the DFS algorithm, but in this exercise you are asked to design an alternative algorithm.)
Hint: How to identify the fist node for the topological order? How to identify subsequent nodes?
For the running time, assume the adjacency-list representation of the graph.
Specify all data structures which your algorithm needs to achieve the O(n + m) running time.
6CCS3OME/7CCSMOME, Lecture 2
25 / 27
Exercises – SGT (cont.)
3. Revise the Breadth-First Search (BFS) algorithm. Trace the execution of BFS on the graph shown below.
4. Revise the Depth-First Search (DFS) algorithm.
Trace the execution of BFS on the graph shown below.
6CCS3OME/7CCSMOME, Lecture 2
26 / 27
a
f
b
k
g
s
h
e
c
d
Exercises – SGT (cont.)
5. The graph below has a negative cycle reachable from the source. Trace the computation of the Bellman-Ford algorithm with FIFO queue on this graph until the PARENT edges form a cycle.
(u, x),
(x, u),
(v, x),
(v, y); (y, v).
(y, s), 6CCS3OME/7CCSMOME, Lecture 2
27 / 27
u −2
1
v
s
5
63
−5
xy 2
Assume that the edges outgoing from nodes are given in this order:
(s, u),
(s, x); (u, v); (x, y);
7
46