[SOLVED] CS algorithm AI 6CCS3OME/7CCSMOME Optimisation Methods

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, Kings College London 2020/21, Second term

Topics
All-pairs shortest-paths problem: find shortest paths for all source-destination pairs of nodes.
Johnsons 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 Dijkstras shortest-paths algorithm
From Dijkstras 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 doesnt, then
nnmatrix 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 wont 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 Dijkstras 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).
Johnsons 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 doesnt work.
Changing weights of edges in Johnsons algorithm:
+M
y
e
e
+M
+z rr z
6CCS3OME/7CCSMOME, Lecture 3
5 / 23
y +y +M+M +xy
+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 Johnsons 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:
ForeachnodevV,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(vk1,vk)
w(v1, v2) + h(v1) h(v2) + w(v2, v3) + h(v2) h(v3) ++w(vk1,vk)+h(vk1)h(vk) w(v1,v2)+w(v2,v3)++w(vk1,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
12 3s12 3
0
42 042
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

Johnsons algorithm
JOHNSON(G, w) { G = (V, E), w edge weights } computeG =(V,E): V =V {s}, E =E{(s,v)|vV}
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 eachvV do h(v)(s,v)
for each(u,v)E do w(u,v)w(u,v)+h(u)h(v) for eachuV do

run DIJKSTRA(G, w, u) to compute (u, v) for all v V

for eachvV do duv (u,v)[h(u)h(v)]
n O(min{n2, m log n}) (n DIJKSTRAS); 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 Johnsons 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 Johnsons 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

Dijkstras 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 Dijkstras 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

Dijkstras 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 Dijkstras 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

Dijkstras 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 Dijkstras algorithm for the single-source (all destinations) case.
6CCS3OME/7CCSMOME, Lecture 3 13 / 23
s
d

Dijkstras algorithm with re-weighting to direct search towards the target
For single-source single-destination shortest-path queries in geographical networks, Dijkstras 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 Dijkstras 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

Dijkstras 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 Dijkstras 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

Dijkstras algorithm with re-weighting: a general setting (2)
Lets 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 w5 c
We can re-weight using estimates b(.): w(u,v) = w(u,v)b(u)+b(v).
We want to apply Dijkstras 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

Dijkstras 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 Dijkstras 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 isnt guaranteed to be the shortest-path weight to t.
6CCS3OME/7CCSMOME, Lecture 3 17 / 23

Dijkstras algorithm with re-weighting A* search algorithm
The modified Dijkstras 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 / doesnt belong, to computed shortest-path trees;
the weight of edge (u, v) increases / decreases.
2. What is the running time of Dijkstras 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 Johnsons alg. doesnt have negative cycles but has a
cycle of weight 0, what are the new weights of the edges on this cycle? 3. Consider Johnsons 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 Johnsons algorithm?
(b) If Johnsons algorithm computes the new edge weights using the Bellman-Ford with FIFO Queue algorithm, then what is the running time of Bellman-Ford in Johnsons algorithm for such an input graph (when all edge weights are non-negative)? Give a precise bound.
4. Consider Johnsons 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 Johnsons 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 Johnsons
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 Dijkstras shortest-paths algorithm, which uses only given original distances of the direct connections, with the computation of Dijkstras 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 straightline distances to d:
10
57 b
7
6
abcdefghijklpqr 21 13 15 0 12 17 6 4 14 18 9 16 11 13 6