代写代考 Algorithms & Data Structures (Winter 2022) Graphs – Single Source Shortest

Algorithms & Data Structures (Winter 2022) Graphs – Single Source Shortest Paths

Announcements
• Deadline.

• Peer review of 3 classmate submissions.

• Introduction.
• Topological Sort. / Strong Connected Components
• Network Flow 1. • Introduction
• Ford-Fulkerson
• Network Flow 2. • Min-cuts
• Shortest Path.
• Minimum Spanning Trees. • Bipartite Graphs.

Shortest Path – Problem
What is the shortest road to go from one city to another?
Example: Which road should I take to go from Montréal to Boston (MA)?
• What is the fastest road?
• What is the cheapest road?

Shortest Path – As a graph problem
• Directed graph G = (V,E) • Weight function w: E➝R
Weightofpathp=⟨v0,v1,…,vk ⟩ n
∑w(vk−1,vk ) k=1
= sum of edges weights on path p
Shortest-path weight u to v:
δ(u,v)=$# $%
Shortest path u to v is any path p such that w(p) = δ(u,v) 5
Generalization of breadth-first search to weighted graphs
p min w(p):u!v
If there exists a path u v. Otherwise.

Shortest Path – As a graph problem – example
Shortest path from s?

Shortest Path – As a graph problem – example
Shortest paths are organized as a tree. Vertices store the length of the shortest path from s.

Shortest Path – As a graph problem – example
Shortest paths are not necessarily unique! 8

Shortest Path – As a graph problem – variants
• Single-source (SSSP): Find shortest paths from a given source vertex s ∈ V to every vertex v ∈ V.
• Single-destination: Find shortest paths to a given destination vertex.
• By reversing the direction of each edge in the graph, you reduce it to SSSP.
• Single-pair: Find shortest path from u to v.
• SSSP solves this variant. All known algorithms for this problem have the same
worst-case asymptotic running time as the best single-source algorithm. • All-pairs: Find shortest path from u to v for all u, v ∈ V .
• By running a SSSP algorithm once from each vertex, but we can solve it faster.

Shortest Path – Negative weight edges
Negative weight edges can create issues.
Why? If we have a negative-weight cycle, we can just keep going around it,
and get w(s, v) = −∞ for all v on the cycle.
When? If they are reachable from the source (Corollary: It is OK to have a
negative-weight cycles if it is not reachable from the source).
What? Some algorithms work only if there are no negative-weight edges in the graph. We must specify when they are allowed and not.

Shortest Path – Cycles
Shortest paths cannot contain cycles:
• Negative-weight: Already ruled out.
• Positive-weight: we can get a shorter path by omitting the cycle.
• Zero-weight: no reason to use them ⇒ assume that our solutions will not use them.
Consequence:
• Since any acyclic path in a graph G = (V,E) contains at most |V|
distinct vertices, it also contains at most |V| – 1 edges. Thus, we can restrict our attention to shortest paths of at most |V| – 1 edges.

Shortest Path – Optimal substructure
subpath of a shortest path is a shortest path.
Proof: (cut and paste) pxy
Suppose this path p is a shortest path from u to v. Then δ(u,v) = w(p) = w(pux) + w(pxy) + w(pyv).

Shortest Path – Optimal substructure
subpath of a shortest path is a shortest path.
Proof: (cont’d) uxyv
Now suppose there exists a shorter path x
Then w(p’xy) v is tense if d(u)+w(u,v)< d(v). If u->v is tense, the tentative shortest path s v is clearly incorrect, because the path s u->v is shorter.
u3vu3v 4946

SSSP – Structure
2. Scan vertices and relax edges.
RELAX(u,v,w)
if d[v]>d[u]+w(u,v) then
d[v] ß d[u]+w(u,v) π[v]ßu
u3vu3v 4946

Shortest Path and Relaxation – Properties
• Triangle inequality
• Foranyedge 𝑢,𝑣 ∈𝐸,wehave𝛿 𝑠,𝑣 ≤𝛿 𝑠,𝑢 +𝑤(𝑢,𝑣).
• Upper-bound property
• We always have d[v] ≥ 𝛿 𝑠,𝑣 for all vertices 𝑣 ∈ 𝑉, and once d[v]
achieves the value 𝛿 𝑠, 𝑣 , it never changes. • No-path property
• Ifthereisnopathfromstov,thenwealwayshaved v =𝛿 𝑠,𝑣 =∞. • Convergence property.
• Ifs u->visashortestpathinGforsome𝑢,𝑣 ∈𝑉,andif𝑑 𝑢 =
𝛿 𝑠,𝑢 at any time prior to relaxing edge (u,v), then 𝑑 𝑣 = 𝛿 𝑠,𝑣 at all time afterwards.
• Path-relaxation property
• If 𝑝 = 𝑣!,𝑣”,…,𝑣# is a shortest path from 𝑠 = 𝑣! to 𝑣#, and we relax the
edges of p in the order 𝑣!,𝑣$ , 𝑣$,𝑣% ,…, 𝑣#&$,𝑣# then 𝑣# 𝑑 = 𝛿 𝑠,𝑣# • Predecessor-subgraph property
• Once 𝑣 𝑑 = 𝛿 𝑠,𝑣 for all 𝑣 ∈ 𝑉 , the predecessor subgraph is a shortest- paths tree rooted at s. 23

SSSP – DAG
DAG ⇒ no negative-weight cycles. DAG-SHORTEST-PATHS(V,E,w,s)
topologically sort the vertices
INIT-SINGLE-SOURCE(V,s)
for each vertex u in topological order do
for each vertex v∈Adj[u] do RELAX(u,v,w)
s2t7 -1y-2z

SSSP – DAG – Example
s2t7 -1y-2z 0∞∞∞∞

SSSP – DAG – Example
s2t7 -1y-2z 026∞∞

SSSP – DAG – Example
61 s2t7 -1y-2z

SSSP – DAG
DAG-SHORTEST-PATHS(V,E,w,s)
topologically sort the vertices
INIT-SINGLE-SOURCE(V,s)
for each vertex u in topological order do
for each vertex v ∈ Adj[u] do RELAX(u,v,w)
Time: (V + E).
Correctness:
O(V+E) O(V)
Because we process vertices in topologically sorted order, edges of any path must be relaxed in order of appearance in the path. ⇒ Edges on any shortest path are relaxed in order.
⇒ By path-relaxation property, correct.

SSSP – Dijkstra’s algorithm
• No negative-weight edges.
• Weighted version of BFS:
• Instead of a FIFO queue, uses a priority queue.
• Keys are shortest-path weights (d[v]).
• Have two sets of vertices:
• S = vertices whose final shortest-path weights are determined,
• Q=priorityqueue=V−S.
• Greedy choice: At each step we choose the light edge.

SSSP – Dijkstra’s algorithm
DIJKSTRA(V,E,w,s) INIT-SINGLE-SOURCE(V,s) S←∅
whileQ≠ ∅ do
u ← EXTRACT-MIN(Q)
S ← S ∪ {u}
for each vertex v ∈ Adj[u] do
RELAX(u,v,w)

SSSP – Dijkstra’s algorithm – Example

Dijkstra’s algorithm – Correctness
Loop invariant:
At the start of each iteration of the while loop, d[v] = δ(s,v) for all v ∈ S. Initialization:
Initially, S = ∅, so trivially true. Termination:
At end, Q=∅ ⇒ S = V ⇒ d[v] = δ(s,v) for all v ∈ V. Maintenance:
Show that d[u] = δ(s,u) when u is added to S in each Iteration.

Dijkstra’s algorithm – Correctness
Show that d[u] = δ(s,u) when u is added to S in each iteration. Suppose there exists u such that d[u] ≠ δ(s,u).
Let u be the first vertex for which d[u] ≠ δ(s, u) when u is added to S. • u≠s,sinced[s]=δ(s,s)=0.
• Therefore,s∈S,soS≠∅.
• There must be some path s u. Otherwise d[u] = δ(s,u) = ∞ by no-
path property.
• So,thereisapaths u. Thus,thereisashortestppaths u.

Dijkstra’s algorithm – Correctness
Show that d[u] = δ(s,u) when u is added to S in each iteration.
Just before u is added to S, the path p connects a vertex in S (i.e., s) to a vertex in V − S (i.e., u).
Let y be the first vertex along p that is in V − S and let x ∈ S be the predecessor of y.
Decompose p into s

Dijkstra’s algorithm – Correctness
Claim 1: d[y] = δ(s, y) when u is added to S. Proof:
x ∈ S and u is the first vertex such that d[u] ≠ δ(s, u) when u is added to S ⇒ d[x] = δ(s, x) when x is added to S.
But when x is added we relax the edge (x, y), so by the convergence property, d[y] = δ(s, y).

Dijkstra’s algorithm – Correctness
Show that d[u] = δ(s,u) when u is added to S in each iteration. Now, we can get a contradiction to d[u] ≠ δ(s, u):
y is on shortest path p (s u), and all edge weights are nonnegative.
⇒ δ(s, y) ≤ δ(s, u)
Then by Claim 1, we have d[y] = δ(s,y) ≤ δ(s,u)
≤ d[u] (upper-bound property)
In addition, y and u were in Q when we chose u, thus d[u] ≤ d[y].
We have d[y] ≤ d[u] & d[u] ≤ d[y] ⇒ d[u] = d[y] . Therefore, d[y] = δ(s, y) ≤ δ(s, u) ≤ d[u] = d[y]
Contradicts assumption that d[u] ≠ δ(s,u).n

Dijkstra’s algorithm – Analysis
DIJKSTRA(V,E,w,s) INIT-SINGLE-SOURCE(V,s) S←∅
while Q ≠ ∅ do
u ← EXTRACT-MIN(Q)
S ← S ∪ {u}
for each vertex v ∈ Adj[u] do
RELAX(u,v,w)
EXTRACT_MIN
DECREASE-KEY

Dijkstra’s algorithm – Analysis
It depends on implementation of priority queue.
If binary heap, each operation takes O(lg V ) time
⇒ O(E lg V ).
Note: We can achieve O(V lg V + E) with Fibonacci heaps.

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts