Lecture20 & 21_AllPairsSP
Wednesday, October 21, 2020 10:47 AM
Review:
Linear programing: generic way to formulate a large class of optimalization problems.
Fisibility version of the problem: drop the optimalizaiton functuion, look at only the constrains, which are bunch of linear inequalities.
Special version of the problem: system of diffiriences. Matrix formulation, every row have 1 and -1 and all other coefficient is zero. Satisfies some unknow variables with subject to a list of different constrains.*
-> equal to graph theory problem: shortest path problem
From any source to any destination Dynamic programing approach
Shortest paths
Single-source shortest paths
• Nonnegative edge weights
○Dijkstra’s algorithm: O(E + V lg V)
• General
○Bellman-Ford algorithm: O(VE)
• DAG
○One pass of Bellman-Ford: O(V + E) (bfs)
All-pairs shortest paths
• Nonnegative edge weights
○Dijkstra’s algorithm |V| times: O(VE + V 2 lg V)
“Use n times”, n = number of vertex • General
○Three algorithms today.
Problem:
Input: Digraph G = (V, E), where V = {1, 2, …, n}, with edge-weight function w : E → R. Output: n × n matrix of shortest-path lengths δ(i, j) for all i, j ∈ V.
Dynamic programming
Analysis of Algorithms Page 1
For the vertex itself: 0 All other things: infinity
For the vertex itself: 0 All other things: infinity
• Based on how many edges do we use in our solution
• A single path graph could have at most n – 1 edges: limit
1. To go from i to j, using at most m edges. We must gone somewhere else using at most m – 1 edges. Then use 1 more edge to arrive at j.
Matrix multiplication
From I to I, the cost is 0 Everybody else we can’t arrive
• Instead of making the summation of product using the product of summations • We are doing n matrix multiplications, Running time: O(n * n3)
* not better than repeatedly perform B-F algorithm
Improved matrix multiplication algorithm
Analysis of Algorithms Page 2
• Negative-weight cycle: starts at I, ends at i. More improvement!
Floyd-Warshall algorithm
Faster dynamic programming
➢Use a different definition
Before based on the number of edges.
Now focus on the vertices: we label the vertices and use the first i vertices (1 to k in i to j)
• Base case: : is there any edge that go from i to j?(0 other vertices are allowed to use)
• General case:
• Critical vertex: there is an unique vertex that labeled k.
Floyd-Warshall recurrence
• To go from I to j, the shortest path either go through vertex k, or it doesn’t. (2 options)
○If it doesn’t, ○If it does,
○ Checking both of them, and pick minimum
Analysis of Algorithms Page 3
Transitive closure of a directed graph
Number of pair for two vertices -> does these exist a path between two vertices?
Graph reweighting
➢Is there a way to adjust weight without changing the problem and in the meantime eliminate negative edge weight for the graph.
• Graph reweighting function h
• For every edge u and v, we have an edge weight w(u,v). We have a function h: wh(u, v)
= w(u, v) + h(u) – h(v)
○How can be pick h values so the result is non-negative
➢Update only the edges between two vertices ➢h(u) – h(v): the difference between the value
Johnson’s algorithm
Based on graph reweighting
Analysis of Algorithms Page 4
1. Try to find a function h (find the shortest path from a dummy source, Bellman-Ford algorithm)
2. Compute the shortest path for the modified function(same shortest path for the original function) [critical step, bottom neck]
3. Take the weight back
➢If E is not n2 this algorithm is better than the Floyd-Warshall
➢Both side of the running time may dominate depends on the circumstance
Analysis of Algorithms Page 5