Lecture17-ShortestPaths1
Sunday, October 18, 2020
5:51 PM
Applications: • Map
• Network browsing •…
Paths in graphs
Minimize the path length among all possible length
• Complexity wise, there is no difference between the first three • The output size of the fourth one is n2
Shortest Path
A shortest path from u to v is a path of minimum weight from u to v. The shortest-path weight from u to v is defined as δ(u, v) = min{w(p) : p is a path from u to v}.
Note: δ(u, v) = ∞ if no path from u to v exists.
Well-definedness of shortest paths
If a graph G contains a negative-weight cycle, then some shortest paths do not exist.
• Keep taking that negative cycle, then the path get shorter and shorter. ➢We assume negative weight doesn’t exist
Optimal substructure
Theorem. A subpath of a shortest path is a shortest path. Proof: cut and phase
If the optimal substructure exist in longest single path problem (allow visit each vertex only once)
Paths in graph
Source
Destination
Single
Single
Single
All
All
Single
All
All
Well-refinedness of shortest paths
Optimal substructure
Analysis of Algorithms Page 1
Triangle inequality
Triangle inequality
Shortest path satisfies.
Theorem. For all u, v, x ∈ V, we have δ(u, v) <= δ(u, x) + δ(x, v).
Single-source shortest paths
(nonnegative edge weights)
Problem. Assume that w(u, v) >= 0 for all (u, v) ∈ E. (Hence, all shortest-path weights
must exist.) From a given source vertex s ∈ V, find the shortest-path weights δ(s, v) for all v ∈ V.
Idea: Greedy.
1. Maintain a set S of vertices whose shortestpath distances from s are known.
2. At each step, add to S the vertex v ∈ V – S whose distance estimate from s is minimum.
Dijkstra
3. Update the distance estimates of vertices adjacent to v.
Dijkstra’s algorithm
only once)
Single -source shortest pahts
Lemma 1
• We can also maintain an arrow based on who changed the value.
Correctness – part I
∈ V –
invariant is maintained over any sequence of relaxation steps.
• d[v] >= δ(s, v) the inequality is maintain through the algorithm, meaning the estimate that we are making always an upper bound of the actural shortest path. And they can never less than the sortest path.
Lemma. Initializing d[s] ← 0 and d[v] ← ∞ for all v {s} establishes d[v] >= δ(s, v) for all v ∈ V, and this
Analysis of Algorithms Page 2
Lemma 2
• Focus on the first violation
Correctness – part II
Lemma. Let u be v’s predecessor on a shortest path from s to v. Then, if d[u] = δ(s, u) and edge (u, v) is relaxed, we have d[v] = δ(s, v) after the relaxation.
Correctness – part III
Theorem. Dijkstra’s algorithm terminates with d[v] = δ(s, v) for all v ∈ V.
Running time analysis:
Theorem: corrctness
Running time analysis
Analysis of Algorithms Page 3
➢Same formula with Prim
What if the edge weight are all 1?
Instead of using priority queue, we can use a queue (simplify the problem, the cost of PQ is complex here.).
Analysis of Algorithms Page 4