6CCS3OME/7CCSMOME Optimisation Methods
Lecture 2
Single-source shortest-paths: Dijkstras algorithm, shortest-paths algorithm for DAGs
Tomasz Radzik and Kathleen Steinho fel
Department of Informatics, Kings College London 2020/21, Second term
Topics
Single-source shortest-paths; restricted cases Only non-negative edge weights allowed:
Dijkstras shortest-paths algorithm
The input graph is acyclic (a DAG a directed acyclic graph): Single-source shortest paths algorithm for DAGs
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
Dijkstras 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
d0
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 Dijkstras 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 Dijkstras 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 relaxed.
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 Dijkstras 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 havent 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 Dijkstras algorithm (2): the crucial property
The crucial property (the invariant of the computation of Dijkstras algorithm):
At the end of each iteration (on the main loop) of Dijkstras algorithm, foreachnodevS, 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 Dijkstras 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 Dijkstras 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 Dijkstras 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 n1mn(n1), 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 Dijkstras algorithm, if Q was maintained
asanorderedlist? (LGT).
6CCS3OME/7CCSMOME, Lecture 2 11 / 27
PriorityQueueimplementedasHeap: operationsandperformance
To improve the running time of Dijkstras 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 Dijkstras 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
Dijkstras algorithm with Heap
The set Q in Dijkstras 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 Dijkstras 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 Dijkstras 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 Dijkstras algorithm with Heap gives the better (worst-case) running time.
In most applications of Dijkstras algorithm, graphs are not dense, so Dijkstras 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 Dijkstras 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 Dijkstras 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 DAGs
Input:
G = (V, E) directed acyclic graph (DAG);
w weights of edges (may be negative);
sV 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 33 p623
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 Dijkstras algorithm slides 4-5.
2. What would be the running time of Dijkstras 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 Dijkstras 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 Dijkstras algorithm for the input graph:
a
(b) Show the shortest-path weights and a shortest-paths tree in this graph.
(c) How to modify Dijkstras 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
Reviews
There are no reviews yet.