6CCS3OME/7CCSMOME – Optimisation Methods
Lecture 3
All-pairs shortest paths
Point-to-point shortest-paths in geographical networks
Tomasz Radzik and Kathleen Steinho ̈fel
Department of Informatics, King’s College London 2020/21, Second term
Topics
• All-pairs shortest-paths problem: find shortest paths for all source-destination pairs of nodes.
Johnson’s algorithm
• Single-source single-destination shortest-path problem
• Geographical networks: geographical coordinates of the nodes are known; the weights of edges are at least the straight-line (geographical) distances between the nodes.
Adaptation of Dijkstra’s shortest-paths algorithm
• From Dijkstra’s algorithm to the A* search algorithm.
6CCS3OME/7CCSMOME, Lecture 3 2 / 23
All-pairs shortest-paths problem
16
19
D E
16
D 16 31 50 0 57 E 34 26 10 18 0
D D A B E D E E
B
Output:
D 16
ABCDE ABCDE ABCDE
A B 15 19 1010 C
15 16 19
A 0 15 34 16 41 A A B A B B 16 0 19 32 26 B B B A B C351902810 CBC EC
A 16 18 C
16
26 19 10
26 B
E 26
26 10 18
E
Input: weighteddirectedgraphG=(V,E). w(v, u) – the weight of edge (v, u).
Assume that the nodes are numbered from 1 to n, that is, V = {1,2,…,n}.
• information whether G contains a negative cycle, and if it doesn’t, then
• n×nmatrix D=(di,j) suchthatdi,j isequaltoδ(i,j)(theshortest-path weight from node i to node j); and
shortest-paths trees, one from each node in the graph.
To avoid technicalities, we won’t discuss computation of shortest-paths trees. 6CCS3OME/7CCSMOME, Lecture 3 3 / 23
Repeatedly apply a single-source shortest-paths algorithm
• If all edge weights are non-negative: • Use Dijkstra’s algorithm.
• The total running time is
n × O(min{m log n, n2}) = O(min{nm log n, n3}).
• No method with a better (worst-case) running time is known. • In the general case, when the edge weights may be negative:
• We may use the Bellman-Ford algorithm.
• If we do so, the total running time is n × O(nm) = O(n2m)
(this is Θ(n4), if m = Θ(n2)).
• The Floyd-Warshall algorithm: Θ(n3).
• Johnson’s algorithm: O(nm log n).
6CCS3OME/7CCSMOME, Lecture 3
4 / 23
Change the weights of edges without changing shortest paths
How can we change the weight of edges (ideally removing negative weights) without changing shortest paths?
Adding the same (large) number
to the weight of each edge doesn’t work.
Changing weights of edges in Johnson’s algorithm:
+M
−y
−e
e
+M
+z −r−r −z
6CCS3OME/7CCSMOME, Lecture 3
5 / 23
y +y +M+M +x−y
+M +M
+r
+c −c c
+M
+M
+e +e
+M x +M
−x
+z
−a
+M +M
+z z
r −c
+a
+x
−z +z
a −a
The main idea behind Johnson’s algorithm
• Reduces the general case (edge weights may be negative) to the case with all edge weights nonnegative.
• Re-weighting: compute new edge weights wˆ with these properties:
1. For all u, v ∈ V , a shortest path from u to v using the original weights w
is also a shortest path from u to v using the new weights wˆ. 2. wˆ(u,v) ≥ 0, for each edge (u,v) ∈ E.
• The general idea for re-weighting:
• Foreachnodev∈V,assignanumberh(v)tov.
• Foreach(v,u)∈E,let wˆ(u,v)=w(u,v)+h(u)−h(v).
• For any numbers h(v), the new edge weights satisfy Property 1 above.
• If there is no negative cycle in G, then we can find numbers h(v) which satisfy also Property 2.
6CCS3OME/7CCSMOME, Lecture 3
6 / 23
Re-weighting
• For any path P = (v1,v2,…,vk):
wˆ(P) = =
wˆ(v1,v2)+wˆ(v2,v3)+···+wˆ(vk−1,vk)
w(v1, v2) + h(v1) − h(v2) + w(v2, v3) + h(v2) − h(v3) +···+w(vk−1,vk)+h(vk−1)−h(vk) w(v1,v2)+w(v2,v3)+···+w(vk−1,vk)+h(v1)−h(vk) w(P) + h(v1) − h(vk) (∗)
= =
• Thus when we change the edge weights from w to wˆ, then for each pair of
nodes u and v, the weight of each path from u to v changes by the same
amount: h(u)−h(v). 25
20
u
v h(v)=8
u
v
h(u)=3
22
17
18
13
• Hence a path P is a shortest path from u to v according to weights w, if and only if, P is a shortest path from u to v according to weights wˆ.
ˆ
• We also have, from (∗): δ(u, v) = δ(u, v) + [h(u) − h(v)].
• How to select numbers h(v), so that all new weights are nonnegative? 6CCS3OME/7CCSMOME, Lecture 3 7 / 23
Computation of the new edge weights – example
input graph
0
s
7 1
−2 3
0
0
−5
0
−4
202
−5 0
0 0
2 −1 344
2
22 34 34
71071
1−2 3s1−2 3
0
−42 0−42
−4
−5
−5
54054 66
0540524 6
Calculate the original and the new weights of paths: 1-3; 1-2-4-3; 1-2-5-4-3. 6CCS3OME/7CCSMOME, Lecture 3
8 / 23
new edge weights
10 0 1313
0
Johnson’s algorithm
JOHNSON(G, w) { G = (V, E), w – edge weights } computeG′ =(V′,E′): V′ =V ∪{s}, E′ =E∪{(s,v)|v∈V}
assign weights to new edges: w(s, v) ← 0, for each v ∈ V
•
return D = duv
Running time: O(nm) (one BELLMAN-FORD);
if BELLMAN-FORD(G′,w,s)=FALSE then
terminate: the input graph G contains a negative cycle
else { BELLMAN-FORD has computed values δ(s, v) } for eachv∈V do h(v)←δ(s,v)
for each(u,v)∈E do wˆ(u,v)←w(u,v)+h(u)−h(v) for eachu∈V do
ˆ
run DIJKSTRA(G, wˆ, u) to compute δ(u, v) for all v ∈ V
ˆ
for eachv∈V do duv ←δ(u,v)−[h(u)−h(v)]
n · O(min{n2, m log n}) (n DIJKSTRA’S); O(n2) (other computation).
Summing up, the total running time is O(min{n3, nm log n }). 6CCS3OME/7CCSMOME, Lecture 3
9 / 23
Correctness of Johnson’s algorithm
1. The input graph G contains a negative cycle, if and only if, there is a negative cycle in graph G′ reachable from s.
This means that the algorithm correctly identifies whether the input graph
has a negative cycle.
a shortest path from s to v
v
2. For each edge (u, v) in G, the new weight wˆ(u, v) assigned to this edge in Johnson’s algorithm is nonnegative. Indeed,
u
δ(s, u) + w(u, v) ≥ δ(s, v)
(the Triangle Inequality for the shortest-path weights), so
a shortest path
wˆ(u,v) = w(u,v)+h(u)−h(v) = w(u,v)+δ(s,u)−δ(s,v) ≥ 0. The nonnegative weights imply that the algorithm correctly computes
ˆ
δ(u, v) for all pairs of vertices.
3. For any numbers h(.) and for each pair of nodes u and v in G: ˆ
δ(u, v) = δ(u, v) − [h(u) − h(v)] (shown earlier)
Thus the algorithm computes correctly δ(u, v) for all pairs of vertices. 6CCS3OME/7CCSMOME, Lecture 3
10 / 23
s
from s to u
Dijkstra’s algorithm for single-source single-destination
• Run Dijkstra from the source and stop when the destination node is considered (is removed from Q). May check the whole network.
s
d
s
d
• Run in parallel two Dijkstra’s computations, one from the source, one from the destinations (considering edges backward). Stop when the shortest
s → d path is found. A smaller part of the network is examined.
How do we know that the combined path (one part from the shortest-path tree from s and the other part from the shortest-path tree to d) is the
shortest s − d path? Implementation is somewhat tricky. 6CCS3OME/7CCSMOME, Lecture 3
11 / 23
Dijkstra’s algorithm for “geographical” networks
•
The nodes are geographical places (say, towns), and we know their coordinates. Theweightsofedges(roaddistances)areatleastthe straight-line distances between the nodes.
How can we use this information to speed-up Dijkstra’s computation for finding a shortest source-destination path?
• •
Use re-weighting of edges to favour the edges leading “geographically” closer to the destination.
The re-weighting with h(v) = −dist(v, d), where dist(v, d) is the straight-line distance from node v to the destination d (computed from the coordinates of v and d):
7
u
5
24
1
3
wˆ(u, v) 27
= w(u, v) − dist(u, d) + dist(v, d) d
(observe that this is always ≥ 0) d
5 3
22 5
26
6CCS3OME/7CCSMOME, Lecture 3
12 / 23
v
=⇒ 10
u
20
Dijkstra’s algorithm with “geographical” re-weighting
• The search for the shortest path is “directed” towards the destination. Only relatively few edges away from the shortest path are considered. This can lead to a considerable improvement of the average running time. But compute the new weights only when you need them!
• The worst-case running time remains as in the main Dijkstra’s algorithm for the single-source (all destinations) case.
6CCS3OME/7CCSMOME, Lecture 3 13 / 23
s
d
Dijkstra’s algorithm with re-weighting to direct search towards the target
• For single-source single-destination shortest-path queries in geographical networks, Dijkstra’s algorithm with re-weighting by the straight-line distances to the destination works because the straight-line distances satisfy the triangle inequality:
dist(u,d) ≤ dist(u,v)+dist(v,d) ≤ w(u,v)+dist(v,d) so the new weights are non-negative:
wˆ(u,v) = w(u,v)−dist(u,d)+dist(v,d) ≥0.
• The straight-line distances are used here as (under)-estimates of the
shortest-path weights.
• Can we use this idea of speeding-up Dijkstra’s algorithm in other context, when we might have some estimates on
the shortest-path weights, but
we cannot guarantee that those estimates
satisfy the triangle inequality? 6CCS3OME/7CCSMOME, Lecture 3
14 / 23
Dijkstra’s algorithm with re-weighting: a general setting (1)
Example:
• The nodes of the graph represent all possible ‘configurations’, say of some game.
c”
An edge from a configuration c′ to
a configuration c′′ represents a possible move, and the weight w(c′, c′′) of this edge represents the cost
of this move (a positive number).
c’ s
c
t
• Find a shortest (least costly) path of moves from a given starting configuration s to a given goal (target) configuration t.
• This is a single-source single-destination shortest-path problem with non-negative edge weights, so we can use Dijkstra’s algorithm, but . . .
• The graph is huge, way too large to be given explicitly as input. The graph is given implicitly by specifying a procedure which for a given configuration generates all possible moves from this configuration.
• We could try Dijkstra, but it would take too much time and memory. 6CCS3OME/7CCSMOME, Lecture 3 15 / 23
Dijkstra’s algorithm with re-weighting: a general setting (2)
• Let’s say for each configuration c
we have an estimate b(c) ≥ 0 on
the cost of getting from c
to the target configuration t, and these etimates are easy to compute.
w’+3 19 w”−5 c”
• We can re-weight using estimates b(.): wˆ(u,v) = w(u,v)−b(u)+b(v).
• We want to apply Dijkstra’s algorithm
to the new weights wˆ(u, v), so that
the computation is directed towards the target.
What should the considerations be here?
6CCS3OME/7CCSMOME, Lecture 3
16 / 23
s
t
20 c’
23 17
15
Dijkstra’s algorithm with re-weighting: a general setting (3)
• Firstly, we probably cannot guarantee non-negative new weights.
set S
c”
u v
• We should therefore use the
modified Dijkstra’s algorithm,
which moves a node back from S to Q, if its shortest-path estimate is updated.
c’ s
t
• In the diagram, if node u is considered
in the current iteration, RELAX(u, v)
may update (reduce) the shortest-path estimate d[v] at v. If d[v] is reduced, then node v is removed form set S and put back to the priority queue Q.
• The modified Dijkstra guarantees that the shortest path to t is eventually found (no negative cycles, so the computation will end successfully), if we compute shortest paths to all nodes.
In other words, we cannot stop the computation when we take the target node t from Q, because the d[t] value at this point of the computation isn’t guaranteed to be the shortest-path weight to t.
6CCS3OME/7CCSMOME, Lecture 3 17 / 23
Dijkstra’s algorithm with re-weighting −→ A* search algorithm
• The modified Dijkstra’s algorithm with re-weighting using a cost estimate function b is the A∗ search algorithm (common in the context of AI methods).
c”
• In the A∗ algorithm, function b(.) is called a heuristic function, and is often denoted by h(.)
• The property of the heuristic function h
which guarantees that when the target
node t is taken from Q, then the shortest path to t is computed:
For each edge (u, v), h(u) ≤ w(u, v) + h(v).
• A heuristic function h(.) which satisfies this property is called consistent or
monotone, and is equivalent to the property that all new weights wˆ(u,v) = w(u,v)−b(u)+b(v)
are non-negative.
6CCS3OME/7CCSMOME, Lecture 3 18 / 23
c’ s
t
Examples and Exercises – LGT
1. For an input graph with no negative edge weights, we have computed all-pairs shortest paths: two output matrices as on slide 3.
One edge (u, v) changes its weight, while all other edge weights remain as they were. What do we have to recalculate to update the all-pairs shortest-path matrices?
Consider cases:
• edge (u, v) belongs / doesn’t belong, to computed shortest-path trees;
• the weight of edge (u, v) increases / decreases.
2. What is the running time of Dijkstra’s algorithm for geographical networks, in terms of n, m, p and q, where n and m are the number of nodes and edges in the graph, respectively, p is the number of iterations (until the destination node is taken from Q), and q is the number of executed relax operations?
In the worst case p = n and q = m, but we would expect p and q to be much smaller than n and m. How should the algorithm be implemented so that the running time depends on p and q, but not on n or m?
6CCS3OME/7CCSMOME, Lecture 3 19 / 23
Examples and Exercises – LGT (cont.)
3. Consider the following problem of maximizing the number of deliveries. The input is a directed graph G = (V, E) with a designated vertex s where a courier is located at time 0.
Each vertex (location) v other than s has a specified fixed time tv > 0 when the message for v should be delivered. That is, if the courier wants to deliver the message at location v, it has to be done exactly at time tv.
Each edge (x, y) of G has a specified travel time w(x, y) > 0: the courier needs w(x, y) time to go from location x to location y.
Design an algorithm for computing a delivery route for the courier which maximises the number of delivered messages.
Further assumptions: (i) the courier can wait, that is, does not have to be constantly moving; (ii) when the courier is at a location v, the delivery of the messages at this location is instantaneous (no any additional time); (iii) the courier can move along the same edges more than once.
Hint: analyse this problem referring to shortest-paths problems and use
appropriate shortest-paths algorithms.
6CCS3OME/7CCSMOME, Lecture 3 20 / 23
Exercises – SGT
1. How does the reweighting change the weights of the cycles?
2. If the input graph for Johnson’s alg. doesn’t have negative cycles but has a
cycle of weight 0, what are the new weights of the edges on this cycle? 3. Consider Johnson’s all-pairs shortest path algorithm and an input graph
with all edge weights non-negative.
(a) What is the relationship between the input weights w and the weights wˆ computed in Johnson’s algorithm?
(b) If Johnson’s algorithm computes the new edge weights using the “Bellman-Ford with FIFO Queue” algorithm, then what is the running time of Bellman-Ford in Johnson’s algorithm for such an input graph (when all edge weights are non-negative)? Give a precise bound.
4. Consider Johnson’s algorithm with the following modification: instead of adding a new vertex s, let s be any vertex of the input graph G.
(a) Give an example of an input graph for which Johnson’s algorithm modified in this way gives incorrect output.
(b) Show that if the input graph is strongly connected (every vertex is
reachable from every other vertex), then the modified Johnson’s
algorithm gives correct output. 6CCS3OME/7CCSMOME, Lecture 3
21 / 23
Exercises – SGT (cont.)
5. For the “geographical” network given below, the starting node p and the destination d, compare the computation of the standard Dijkstra’s shortest-paths algorithm, which uses only given original distances of the direct connections, with the computation of Dijkstra’s algorithm which uses the geographical re-weighting. The straight-line distances from all nodes to the destination node d are given below.
In both cases, show the shortest paths tree at the termination of the computation, that is, at the time when the destination node d is taken from the priority queue. Indicate also all edges to which the relax operation has been applied.
Note that the original distances are the same in both directions of an edge, but the re-weighted distance of an edge (x, y) may be different than the re-weighted distance of the reverse edge (y, x).
6CCS3OME/7CCSMOME, Lecture 3 22 / 23
Exercises – SGT (cont.)
5. (cont.)
f
6
h
6CCS3OME/7CCSMOME, Lecture 3
23 / 23
e 36
3 r
4
d
4 j9
9
g 3p4
3
c
5
6 5
i 2
l3 4
7
k
7 a
q
9 straight−line distances to d:
10
57 b
7
6
abcdefghijklpqr 21 13 15 0 12 17 6 4 14 18 9 16 11 13 6