CS代考 Lecture 22: Shortest Paths Cont.

Lecture 22: Shortest Paths Cont.
• Quick Review of Previous Class
• Concept of Edge Relaxation
Relax(u,v)

Copyright By PowCoder代写 加微信 powcoder

• Bellman-Ford Algorithm: relax all edges V-1 times in arbitrary order .
• Shortest path in a Directed Acyclic Graph: relax all edges exactly once in topological order .
• Algorithms work with negative weights.
• Shortest paths are not applicable for negative cycles.

• Single Source Shortest Path • Dijkstra Algorithm
• All-Pairs Shortest Paths • First DP Formulation
• 2nd DP Formulation
• Floyd-Warshall

SPs in a graph with cycles and nonnegative weights
Dijkstra’s algorithm.
 Maintain a set of explored nodes.
Initialize Assume we know,
Key lemma: If all edges leaving were already relaxed, let be the vertex in with the minimum . Then ,
– This can then be added to , and process repeated.
minimum 𝑣. 𝑑 among nodes not in 𝑆

Dijkstra’s Algorithm
Dijkstra(𝐺, 𝑠): for each 𝑣∈𝑉 do
𝑣. 𝑑 ← ∞,𝑣. 𝑝 ← 𝑛𝑖𝑙,𝑣. 𝑐𝑜𝑙𝑜𝑟 ← 𝑤h𝑖𝑡𝑒 𝑠. 𝑑 ← 0
insert all nodes into a min-heap 𝑄 with 𝑑 as key while 𝑄≠∅
𝑢 ← Extract-Min(𝑄)
𝑢. 𝑐𝑜𝑙𝑜𝑟 ← 𝑏𝑙𝑎𝑐𝑘
for each 𝑣 ∈ 𝐴𝑑𝑗[𝑢] do
% relax all edges leaving 𝑣 if 𝑣.𝑐𝑜𝑙𝑜𝑟 = 𝑤h𝑖𝑡𝑒 and 𝑢.𝑑 + 𝑤(𝑢,𝑣) < 𝑣.𝑑 then 𝑣.𝑑←𝑢.𝑑+𝑤 𝑢,𝑣 Decrease-Key(𝑄, 𝑣, 𝑣. 𝑑) Running time:  Very similar to Prim’s algorithm Analysis Assumption: 𝐺isconnectedso𝑉=𝑂 𝐸 . Dijkstra’s Algorithm: Example Note: All the shortest paths found by Dijkstra’s algorithm form a tree (shortest-path tree). Exercise on Most Reliable Paths Consider a directed graph corresponding to a communication network. Each edge (u,v) is associated with a reliability value r(u,v), that represents the probability that the channel from from u to v will not fail. Assume that the edge probabilities are independent. Modify Dijkstra’s algorithm to find the most reliable path between a node s and every other vertex. Set d[s]=1, and d[u]=0  us Insert all vertices in a max heap Q on d[u] While Q is not empty u=Extract-max(Q) For each edge (u,v) // v is in the adjacency list of u If d[u]r(u,v) > d[v] // relax (u,v) d[v]=d[u]  r(u,v)
Increase-key (Q,v,d[v])
Set u to be the predecessor of v

Consider a shortest path 𝑃 from 𝑠 to 𝑣.
Dijkstra’s Algorithm: Correctness
Lemma. Suppose relaxed. Then
for all , and all edges leaving have been
, where is the vertex with minimum in .
(assume 𝑣. 𝑑 ≠ 𝛿 𝑠, 𝑣 )
starts Whenever is updated, it’s because a path
Pf. (by contradiction)
 Note that with distance Thus if
was found. So always have
– Suppose𝑥→𝑦isthefirstedgeon𝑃 that takes 𝑃 out of 𝑆.
– 𝑃 is a shortest path => its subpath (𝑠, … , 𝑥, 𝑦) must also be a shortest path,
– Since𝑥∈𝑆,wehave𝑥.𝑑=𝛿 𝑠,𝑥 .
– The edge 𝑥 → 𝑦 has been relaxed, so 𝑦.𝑑 ≤ 𝑥.𝑑 + 𝑤(𝑥,𝑦).
=> 𝑥.𝑑+𝑤 𝑥,𝑦 =𝛿(𝑠,𝑦).
– 𝛿 𝑠, 𝑦 ≤ 𝛿(𝑠, 𝑣), assuming nonnegative weights
=> 𝑣.𝑑>𝛿 𝑠,𝑣 ≥𝛿 𝑠,𝑦 = 𝑥.𝑑+𝑤 𝑥,𝑦 ≥ 𝑦.𝑑,
contradicting factthat𝑣.𝑑isthesmallestin𝑉−𝑆.

Dijkstra fails with Negative Weights
Dijkstra would calculate 𝛿 𝑠, 𝑡 = 1, but correct answer is 𝛿 𝑠,𝑡 = −1.
Re-weighting. Might think that this can be “fixed” by adding a constant to every edge weight. This doesn’t work.
Add 3 to every weight. Dijkstra would find shortest s-t path is s-u-v, but shortest s-t path in original graph is s-v-w-t.

A* for s-t shortest path We wish to find the shortest path between s and t.
Assume that the weight of each edge (u,v) corresponds to the length of the road connecting them. Then, between any node u and t, is their network distance. Let be the Euclidean distance between u and t. Then, ≤ .
Dijkstra extracts from the min heap the node u that minimizes d[u], i.e., the network distance
A*-search extracts from the min heap the node u that minimizes: d[u]+ , i.e., it guides search towards the destination. It terminates when we reach the destination node t.
A* can be used with any function provided that ≤ . Faster than Dijkstra in practice, but asymptotically the same.
Dijkstra visited nodes
A*-visited nodes

Other fast algorithms s-t shortest path
Bidirectional: start Dijkstra expansions from both s and t in parallel. When you find a common node u in both expansions, stop. The shortest path has distance: + .
Can also be combined with A*.
Continuous monitoring of shortest path: the previous algorithms return a one-time path, assuming fixed edge weights. Real navigation systems monitor the traffic conditions and continuously update your path when traffic conditions change (e.g., accidents).
Many later algorithms for s-t paths (based on contraction hierarchies, partial materialization, landmarks etc) are much faster than Dijkstra in practice.

, for all pairs of nodes .
A data structure from which the shortest path from extracted efficiently, for any pair of nodes
All-Pairs Shortest Paths
 Directed graph .
 Weight length of edge .
– Note: Storing all shortest paths explicitly for all pairs requires space.
Graph representation
 Assume adjacency matrix
– can be extracted in time.
– , ifthereisnoedgefrom to .
 If the graph is stored in adjacency lists format, can convert to adjacency matrix in 􏰈 time.

Using previous algorithms
When there are no negative cost edges
 Apply Dijkstra’s algorithm to each vertex (as the source).
 Recall that Dijkstra algorithm runs in
 This gives an -time algorithm
If the graph is dense, this is 􏰏 .
When negative-weight edges are present
 The Bellman-Ford algorithm permits negative edges and solves the single-source shortest path problem in time
– Run the B-F algorithm from each vertex.
􏰈 time, which is 􏰚 for dense graphs.

Dynamic Programming: Solution 1
Def: (􏰦) length of the shortest path from 􏰌􏰙
to that contains at
most edges.
Use (􏰦) to denote the matrix Recurrence:
For some 𝑘, let 𝑃′ be the shortest path from𝑖to𝑘containingatmost𝑚−1edges.
𝑑(􏰦􏰓􏰆) 􏰌􏰋􏰉
𝑙𝑒𝑛𝑔𝑡h𝑃􏰧 =𝑑
Then 𝑃′ followed by 𝑗 is a path from
from 𝑖 to 𝑗 containing at most 𝑚 edges and
has length 𝑑(􏰦􏰓􏰆)+𝑤(𝑘,𝑗) 􏰌􏰋
𝑑(􏰦􏰓􏰆) 􏰌􏰋􏰊
1 𝑤 𝑘􏰆,𝑗 𝑤 𝑘􏰀, 𝑗
𝑑(􏰦􏰓􏰆) 􏰌􏰋􏰔
(􏰦) (􏰦􏰓􏰆) 􏰌􏰙 􏰆􏰜􏰋􏰜􏰀 􏰌􏰋

(􏰦) to denote the matrix
Use Recurrence:
Solution 1: Algorithm
Def: (􏰦) length of the shortest path from to
that contains at
Goal: (􏰀􏰓􏰆), since no shortest path can have more than
(􏰦􏰓􏰆) 􏰆􏰜􏰋􏰜􏰀 􏰌􏰋
Slow-All-Pairs-Shortest-Paths(𝐺): 𝑑(􏰆) =𝑤(𝑖,𝑗) for all 1≤𝑖,𝑗≤𝑛
for 𝑚←2 to 𝑛−1
let 𝐷(􏰦) be a new 𝑛×𝑛 matrix for 𝑖←1 to 𝑛
return 𝐷(􏰀􏰓􏰆)
for 𝑗←1 to 𝑛 𝑑(􏰦) ← ∞
for 𝑘←1 to 𝑛
if 𝑑(􏰦􏰓􏰆) +𝑤 𝑘,𝑗 <𝑑(􏰦) then 𝑑(􏰦) ←𝑑(􏰦􏰓􏰆) +𝑤 𝑘,𝑗 􏰌􏰋 􏰌􏰙 􏰌􏰙 􏰌􏰋 Analysis: 􏰚 time, 􏰏 space, can be improved to 􏰈 Example of Solution 1 Algorithm starts with 𝐷(􏰆), initial edge lengths It then iteratively constructs 𝐷(􏰈), 𝐷(􏰏), 𝐷(􏰚) 𝐷(􏰚) is the final solution, containing all shortest path lengths. A Deeper Dive Consider shortest path from 3 -> 5

A Deeper Dive
Consider shortest path from 3 -> 5
𝑑􏰆 3,5 =∞ 𝑑􏰈 3,5 =11

A Deeper Dive
Consider shortest path from 3 -> 5
𝑑􏰆 3,5 =∞ 𝑑􏰈 3,5 =11
𝑑􏰏 3,5 =11

A Deeper Dive
Consider shortest path from 3 -> 5
𝑑􏰆 3,5 =∞ 𝑑􏰈 3,5 =11
𝑑􏰏 3,5 =11 𝑑􏰚 3,5 =3

Dynamic Programming: Solution 2
Observation:
To compute (􏰦), instead of looking at the last stop before , we 􏰌􏰙
look at the middle point.
 This cuts down the problem size by half.
New recurrence:
(􏰈􏰴) (􏰴) (􏰴) 􏰌􏰙 􏰆􏰜􏰋􏰜􏰀 􏰌􏰋 􏰋􏰙
Algorithm:
Calculating each matrix takes
(􏰆) (􏰈) (􏰚) (􏰹)
􏰏 time: total time
Q: This might overshoot (􏰀􏰓􏰆). Is algorithm still correct?
A: It’s OK. (􏰀􏰧) 􏰧 contains length of shortest paths with at most 􏰧 edges; it will not miss any shortest path with up to edges.
Actually, (􏰀􏰧) (􏰀􏰓􏰆) for any 􏰧 , since no shortest path has more than edges.

Solution 3: Floyd-Warshall
Def: (􏰋) length of the shortest path from to that such that all
intermediate vertices on the path (if any) are in the set
𝑑(􏰇) = ∞ 􏰛,􏰥
Initially: 𝑑􏰌􏰙􏰇 Goal: 𝐷(􏰀)

Solution 3: Floyd-Warshall
Def: (􏰋) length of the shortest path from to that such that all 􏰌􏰙
intermediate vertices on the path (if any) are in the set .
𝑑(􏰇) = ∞ No Path 􏰛,􏰥
𝑑(􏰆) =13 (516) 􏰛,􏰥
Initially: 𝑑􏰌􏰙􏰇 Goal: 𝐷(􏰀)

Solution 3: Floyd-Warshall
Def: (􏰋) length of the shortest path from to that such that all
intermediate vertices on the path (if any) are in the set
𝑑(􏰈) = 9 3 􏰛,􏰥
𝑑(􏰇) = ∞ No Path 􏰛,􏰥
𝑑(􏰆) =13 (516) 􏰛,􏰥
Initially: 𝑑􏰌􏰙􏰇 Goal: 𝐷(􏰀)

Solution 3: Floyd-Warshall
Def: (􏰋) length of the shortest path from to that such that all 􏰌􏰙
intermediate vertices on the path (if any) are in the set .
Initially: 𝑑􏰌􏰙􏰇 Goal: 𝐷(􏰀)
𝑑(􏰈) = 9 􏰛,􏰥
𝑑(􏰏) = 8 􏰛,􏰥
𝑑(􏰇) = ∞ No Path 􏰛,􏰥
𝑑(􏰆) =13 (516) 􏰛,􏰥

Solution 3: Floyd-Warshall
Def: (􏰋) length of the shortest path from to that such that all 􏰌􏰙
intermediate vertices on the path (if any) are in the set .
𝑑(􏰈) = 9 􏰛,􏰥
𝑑(􏰏) = 8 􏰛,􏰥
𝑑(􏰚) =6 􏰛,􏰥
(5 2 6) (5 3 2 6) (5416)
𝑑(􏰇) = ∞ No Path 􏰛,􏰥
𝑑(􏰆) =13 (516) 􏰛,􏰥
Initially: 𝑑 􏰇
􏰌􏰙 Goal: 𝐷(􏰀)

Recurrence
(􏰋) 􏰋􏰓􏰆 􏰋􏰓􏰆 (􏰋􏰓􏰆) 􏰌􏰙 􏰌􏰙 􏰌􏰋 􏰋􏰙
When computing (􏰋), there are two cases: 􏰌􏰙
 Case 1: is not a vertex on the shortest path from to => then the path uses only vertices in
 Case 2: is an intermediate node on the shortest path from to ,
=> path can be split into shortest subpath from to and a subpath from to .
Both subpaths use only vertices in
􏰋􏰓􏰆 􏰋􏰓􏰆 􏰌􏰋 􏰋􏰙

Floyd-Warshall Algorithm
Floyd-Warshall(𝐺):
𝑑(􏰇) =𝑤(𝑖,𝑗) for all 1≤𝑖,𝑗≤𝑛
for 𝑘←1 to 𝑛
let 𝐷(􏰋) be a new 𝑛×𝑛 matrix for 𝑖←1 to 𝑛
for 𝑗←1 to 𝑛
if 𝑑(􏰋􏰓􏰆) + 𝑑(􏰋􏰓􏰆) < 𝑑(􏰋􏰓􏰆) then 􏰌􏰋 􏰋􏰙 􏰌􏰙 𝑑(􏰋) ← 𝑑(􏰋􏰓􏰆) + 𝑑(􏰋􏰓􏰆) 𝑑(􏰋) ← 𝑑(􏰋􏰓􏰆) 􏰌􏰙 􏰌􏰙 return 𝐷(􏰀) 􏰏 space, but can be improved to 􏰈 Surprising discovery: If we just drop all the superscripts, i.e., the algorithm just uses one array , the algorithm still works! (why?) Floyd-Warshall Algorithm: Final Version Floyd-Warshall(𝐺): 𝑑􏰌􏰙 =𝑤(𝑖,𝑗) and 𝑖𝑛𝑡𝑒𝑟𝑚𝑒𝑑 𝑖,𝑗 ←0 for all 1≤𝑖,𝑗≤𝑛 for 𝑘←1 to 𝑛 for 𝑖←1 to 𝑛 for 𝑗←1 to 𝑛 if 𝑑􏰌􏰋 + 𝑑􏰋􏰙 < 𝑑􏰌􏰙 then 𝑑􏰌􏰙 ← 𝑑􏰌􏰋 + 𝑑􏰋􏰙 𝑖𝑛𝑡𝑒𝑟𝑚𝑒𝑑𝑖,𝑗 ←𝑘 time space The array records one intermediate node on the shortest pathfrom to .  It is if the shortest path does not pass any intermediate nodes. Extracting Shortest Paths Path(𝑖, 𝑗): if 𝑖𝑛𝑡𝑒𝑟𝑚𝑒𝑑 𝑖, 𝑗 = 𝑛𝑖𝑙 then output (𝑖,𝑗) else Path(𝑖, 𝑖𝑛𝑡𝑒𝑟𝑚𝑒𝑑[𝑖, 𝑗]) Path(𝑖𝑛𝑡𝑒𝑟𝑚𝑒𝑑 𝑖,𝑗 ,𝑗) Path(2,3) 𝑖𝑛𝑡𝑒𝑟𝑚𝑒𝑑[2,3] = 6 Path(2,6) 𝑖𝑛𝑡𝑒𝑟𝑚𝑒𝑑[2,6] = 5 Path(6,3) 𝑖𝑛𝑡𝑒𝑟𝑚𝑒𝑑[6,3] = 4 Path(2,5) Path(5,6) Output (2,5) Output (5,6) Output (6,4) Output (4,3) Running time: O(length of the shortest path) Path(6,4) Path(4,3) Exercise on Detection of Negative Cycles Given a directed weighted graph G(V,E), use Floyd-Warshall in order to find if a graph has negative cycles  Assume that w(i,i) = 0, for each vertex i graph G Negative cycle 112112 1111 4-33 4-33 Solution for Negative Cycles First solution Lets consider the smallest negative cycle C (i.e., the one involving the smallest number of vertices). Let k be the highest-numbered vertex in C, and i be any other vertex in C. Then, d(k)ii=min{d(k-1)ii, d(k-1)ik + d(k-1)ki} < 0 Since d(k+1)ii,...,d(n)ii never increases, d(n)ii is also negative. Therefore, we check the diagonal of the last distance matrix D(n) produced by Floyd-Warshall, and if there is a d(n)ii < 0, we can conclude that there is a negative cycle. Second solution Run Floyd-Warshall for one extra iteration. If there is a negative cycle, some distances will decrease and D(n+1)D(n). Exercise on Transitive Closure Given a directed unweighted graph G(V,E), we want to generate G*(V,E*), where E*={(i,j): there is a path from vertex i to j in G}  Input: an adjacency matrix A of G: – a(i,j)=1 if there is an edge from vertex i to j in G – a(i,j)=0 if there is no edge from vertex i to j in G  Output: an adjacency matrix A* of G*: – a*(i,j)=1 if there is a path from vertex i to j in G – a*(i,j)=0, otherwise graph G 1212 4343 transitive closure G* Solution 1 on Transitive Closure We first derive the weight matrix as follows  w(i,j) = 1, if a(i,j)= 1  w(i,j) = , if a(i,j)= 0 Apply Floyd-Warshall and obtain shortest distance matrix D(n) d(n)ij is the length of the shortest path from vertex i to j in G, in terms of the number of edges. If d(n)ij < , set a*(i,j)= 1 If d(n)ij = , set a*(i,j)= 0 Solution 2 on Transitive Closure Based on Boolean Operators Define boolean matrix T(0)=A t = a(i,j) Optimal substructure (k)ij (k-1)ij (k-1)ik (k-1)kj t =t (t t ) Asymptotic complexity same as that of Floyd-Warshall (n3) However, more efficient in practice because boolean operators faster than arithmetic operators Needs less space for the boolean matrix (instead of the distance matrix) 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com