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