Lecture 21: Shortest Paths
• Single Source Shortest Path • Bellman-Ford Algorithm
• Shortest Paths in a DAG
Copyright By PowCoder代写 加微信 powcoder
• Shortest Paths
Shortest Path Algorithms
Running Time
Space Used
Bellman-Ford
Single-Source
Single-Source DAG
Single-Source Non-Neg Weights
All-Pairs 1
Adj Matrix
All-Pairs 2
Adj Matrix
Floyd-Warshall
Adj Matrix
Space Used is in addition to space required to store the graph.
Shortest Path Problem
Directed graph .
– An undirected edge can be considered as two directed edges.
Source , destination .
Weight length of edge (𝑤 𝑒 can be negative)
Shortest path problem: Find the shortest path from Def: the distance from to , is
the length of the shortest path from to
20 31511419 56
14 18 6 62
Shortest Path Problem
Directed graph .
– An undirected edge can be considered as two directed edges.
Source , destination .
Weight length of edge (𝑤 𝑒 can be negative)
Shortest path problem: Find the shortest path from Def: the distance from to , is
the length of the shortest path from to
20 31511419 56
14 18 6 62
𝛿(𝑠,𝑡)= 9+23+2+16 = 50.
Shortest Path Problem
Directed graph .
– An undirected edge can be considered as two directed edges.
Source , destination .
Weight length of edge (𝑤 𝑒 can be negative)
Shortest path problem: Find the shortest path from to . Single-source shortest path: Find the shortest path from
to every node.
Shortest path from s to x
20 31511419 56
14 18 6 62
Shortest Paths: Negative Weight Cycles
Negative weight cycles.
Note. The shortest path problem is not well defined if the graph contains negative-weight cycles.
(Repeating C can create arbitrarily negative s-t paths.)
So we will always assume no negative cycles exist.
Pf: (by contradiction)
Suppose the subpath
i.e., there is another path
is not the shortest
from to that is shorter than .
path. Impossible!
Then we can replace with
This contradicts the choice of as a shortest
this creates , a
Same proof works for the subpath from to .
Lemma (Cut and Paste Argument):
Let be a shortest path. Then the subpaths
must also be, respectively, shortest and paths.
path shorter than
Concept of Relaxation
Let be shortest distance found so far from starting node to node , and
be the last node in the current shortest path from
Relaxing edge means checking whether taking shortest path to and then edge
gives an even shorter path to improving known shortest path to
If this occurs, we update
Old candidate shortest path
Relax(u,v)
v.p u w(u,v) v
New candidate shortest path
Bellman-Ford Algorithm
Initially, we set v.d = for all nodes,
except the starting node s for which v.s = 0
Relax all edges once, in no particular order.
After finishing, v.d < for all neighbors of s, or equivalently for all nodes that are connected with s through a path with length 1 edge.
Relax all edges a 2nd time (in no particular order).
After finishing, v.d < for all nodes that can be reached from s through a path with length 1 or 2. A relaxation, may only decrease distances so v.d is the shortest distance for paths with maximum length 2.
In general, after relaxing all edges for the i-th time, v.d is the shortest distance for paths with maximum length i edges.
Assuming no negative cycles, what is the max number of edges in a path?
A path may have at most V-1 edges.
Thus, after relaxing all edges V-1 times, v.d is the actual shortest
distance between v and s.
Bellman-Ford– Basic Implementation
Shortest-Path(𝐺, 𝑠): for each node 𝑣∈𝑉 do
for 𝑖←1 to 𝑉−1
for each edge 𝑢,𝑣 ∈𝐸
if 𝑢.𝑑+𝑤𝑢,𝑣 <𝑣.𝑑 then
𝑣. 𝑑 ← 𝑢. 𝑑 + 𝑤(𝑢, 𝑣) 𝑣. 𝑝 ← 𝑢
Relax(𝑢, 𝑣)
Analysis. time, space.
Bellman-Ford as Dynamic Programming
Def. length of shortest path from to using up to edges.
Recurrence:
Suppose is the last edge of the shortest path from to . By the cut and paste argument, the subpath from to must also be shortest, using at most edges, followed by .
Final solution: length of the actual shortest path from
to , since no shortest path can have edges or more.
Bellman-Ford uses a single instead of – After the -th iteration,
Bellman-Ford: Efficient Implementation
Bellman-Ford(𝐺, 𝑠): for each node 𝑣∈𝑉 𝑣.𝑑 ← ∞,𝑣.𝑝 ← 𝑛𝑖𝑙
for 𝑖←1 to 𝑉−1
for each node 𝑢∈𝑉
if 𝑢.𝑑 changed in previous iteration then
for each 𝑣 ∈ 𝐴𝑑𝑗[𝑢]
if 𝑢.𝑑+𝑤 𝑢,𝑣 <𝑣.𝑑 then
𝑣.𝑑 ← 𝑢.𝑑 + 𝑤(𝑢,𝑣) Relax(𝑢,𝑣)
if no 𝑣.𝑑 changed in this iteration then terminate
time in the worst case, but can be much faster in practice space.
Can be run in parallel.
Used on massive graphs (even if no negative edges).
Can also detect whether there is a negative cycle.
Exercise Bellman-Ford for Negative Cycle Detection
How you can use Bellman-Ford to detect cycles?
Assuming no negative cycles, the max number of edges in a path is V-1. What happens if there are negative cycles?
Some nodes distances will continue decreasing after relaxing all edges for V times.
Apply Bellman-Ford and add another round of relaxations:
For each edge (u,v) // check for negative cycles If d[u]+w(u,v) < d[v] then return “Negative Cycle”
By subpath optimality, we have
Shortest path in a DAG
Input is a DAG, a Directed Acyclic Graph
will store shortest path distance from
Unlike in Bellman-Ford, each edge will only be relaxed once.
We need to ensure that when v is processed,
ALL u with ( , ) have already been processed,
so holds the correct value when v is processed,
We can do that by processing v (and thus the ) in the topological order of the nodes.
Shortest path in a DAG: algorithm
DAG-Shortest-Path(𝐺, 𝑠)
topologically sort the vertices of 𝐺 for each vertex 𝑣 ∈ 𝑉
𝑣. 𝑝 ← 𝑛𝑖𝑙 𝑠. 𝑑 ← 0
for each vertex 𝑢 in topological order for each vertex 𝑣 ∈ 𝐴𝑑𝑗[𝑢]
if 𝑣.𝑑>𝑢.𝑑+𝑤(𝑢,𝑣) then
𝑣.𝑑 ← 𝑢.𝑑 + 𝑤(𝑢,𝑣) Relax(𝑢,𝑣) 𝑣. 𝑝 ← 𝑢
Running time:
Can find the actual shortest path by tracing the parent pointers.
If we just want to find the shortest path from to , can stop the
algorithm when But this does not reduce the running time asymptotically.
Exercise on Longest Path in DAG
Given a directed acyclic graph with real-valued edge weights and two vertices s, t, describe a dynamic programming algorithm for finding the longest weighted simple path from s to t.
Longest part:
s, b, a, d, t
Total weight= 1+2+4+3=10
Let ld[v] be the weight of the longest path from s to v: ld[v]= 0 , if s = v
ld[v]= max(u,v)E{w(u,v)+ld[u])}, otherwise
How do we make sure that when we reach v, we have computed the longest
distance for every u such that there is an edge (u,v)? Answer: We use topological sort starting from s.
Algorithm on Longest Path in DAG
DP-LD(G, s, t)
Topologically sort the vertices of G, starting from s For each vertex v, set ld[v]=-
For each vertex u in the topological order
For each vertex v in adjacency list of u if ld[u] + w(u,v) > ld[v]
ld[v]= ld[u] + w(u,v)
topological sort
Running time (V+E)
a2b bld[b]=1
ld[d]=7 ld[t]=10
Exercise on Critical Paths
Let G = (V,E) be a DAG, where vertices correspond to jobs and edges are sequence constraints: (u,v) means that job u should be performed before v (in other words, u must finish before v starts). Each vertex is associated with a positive weight that indicates the time to complete the corresponding job.
Find the minimum time to perform all the jobs.
For instance, in the following graph, to finish d, we must first complete a and c;
total time 9 (4 for d and 5 for a; c can be performed in parallel with a). Minimum time is the time required to finish f, i.e., 15.
Solution by Longest Path I generate a new graph G'(V’,E’) as follows.
I add a new vertex s so that V’ = V {s}.
All edges in E are included in E’.
I add an edge from s to each vertex that has in-degree 0; (only s vertex has in-degree 0 in E’).
Then, I assign the weight of each edge (u,v) to be the weight of v. Thus, |V’|=|V|+1 and |E’||E|+|V| (since no more than |V| vertices have in-degree 0).
The earliest time that I can finish all jobs corresponds to the longest path in G’.
Exercise on Longest Increasing Subsequence
Input: a sequence of numbers: a1, a2,…, an Example:5,2,8,6,3,6,9,7
Increasing sequence : 5, 2, 8, 6, 3, 6, 9, 7
Longest increasing sequence : 5, 2, 8, 6, 3, 6, 9, 7 or 5, 2, 8, 6, 3, 6, 9, 7
Convert to a directed graph G(V,E)
V={a , a ,…, a } 12n
E={(a ,a)/i