程序代写代做代考 algorithm C graph Analysis of Algorithms

Analysis of Algorithms
Negative-weight cycles
Negative-weight cycles
for each edge (u, v) ∈ E
do if d[v] > d[u] + w(u, v)
C 5 D
LECTURE 23
Recall: If a graph G = (V, E) contains a negative- weight cycle, then some shortest paths may not exist.
Recall: If a graph G = (V, E) contains a negative- weight cycle, then some shortest paths may not exist.
Shortest Paths II
Example:

• Bellman-Ford algorithm • Linear programming and
difference constraints
• VLSI layout compaction
u
v u v
Bellman-Ford algorithm
Example of Bellman-Ford Example of Bellman-Ford
d[s] ← 0
for each v ∈ V – {s}

initialization
do for each edge (u, v) ∈ E A
do d[v] ← ∞ for i ← 1 to |V| – 1
BB
do if d[v] > d[u] + w(u, v) relaxation A then d[v] ← d[u] + w(u, v) step
1
E
A
1
E
then report that a negative-weight cycle exists At the end, d[v] = δ(s, v), if no negative-weight cycles.


Time = O(VE).
4
–3
4
–3
Example: … <0 <0 123 –1 B 2 0 –1 B 2 ∞ 3 2 E A 3 2 E CD CD C 5 D 456 Example of Bellman-Ford Example of Bellman-Ford Example of Bellman-Ford ∞∞∞ B1B1B1 –1 B 2 –1 B 2 –1 B 2 073∞ 073∞ 073∞ A43 2E A43 2E A43 2E A5 18E A5 18E A5 18E 222 4 C 6 D –3 4 C 6 D –3 4 C 6 D –3 C5D C5D C5D ∞∞∞∞∞∞ Order of edge relaxation. 789 Bellman-Ford algorithm: Finds all shortest-path lengths from a source s ∈ V to all v ∈ V or determines that a negative-weight cycle exists. Initialization. Example of Bellman-Ford Example of Bellman-Ford Example of Bellman-Ford ∞ −∞1 −1 B1B1B1 –1 B 2 –1 B 2 –1 B 2 073∞ 073∞ 073∞ A43 2E A43 2E A43 2E A5 18E A5 18E A5 18E 222 4 C 6 D –3 4 C 6 D –3 4 C 6 D –3 C5D C5D C5D ∞ ∞ ∞ ∞ ∞4 ∞ 10 11 12 Example of Bellman-Ford Example of Bellman-Ford Example of Bellman-Ford −1 −1 −1 B1B1B1 –1 B 2 –1 B 2 –1 B 2 073∞ 073∞ 073∞ A43 2E A43 2E A43 2E A5 18E A5 18E A5 18E 222 4 C 6 D –3 4 C 6 D –3 4 C 6 D –3 C5D C5D C5D 4 ∞ 42 ∞ 2 ∞ 13 14 15 Example of Bellman-Ford Example of Bellman-Ford Example of Bellman-Ford −1 −1 −1 B1B1B1 –1 B 2 0 7 3 ∞ –1 B 2 0 7 3 ∞1 –1 B 2 0 7 3 1 A43 2E A5 18E A43 2E A5 18E A43 2E A5 18E 222 4 C 6 D –3 4 C 6 D –3 4 C 6 D –3 C5D C5D C5D 2∞2∞2∞ End of pass 1. 16 17 18 Example of Bellman-Ford Example of Bellman-Ford Example of Bellman-Ford −1 −1 −1 B1B1B1 –1 B 2 –1 B 2 –1 B 2 0731 0731 0731 A43 2E A43 2E A43 2E A5 18E A5 18E A5 18E 222 4 C 6 D –3 4 C 6 D –3 4 C 6 D –3 C5D C5D C5D 2 ∞1 2 1 2 1 19 20 21 Example of Bellman-Ford Example of Bellman-Ford Example of Bellman-Ford −1 −1 −1 B1B1B1 –1 B 2 –1 B 2 –1 B 2 0731 0731 0731 A43 2E A43 2E A43 2E A5 18E A5 18E A5 18E 222 4 C 6 D –3 4 C 6 D –3 4 C 6 D –3 C5D C5D C5D 2 1 2 1 2 −12 Example of Bellman-Ford Correctness Correctness −1 Theorem. If G = (V, E) contains no negative- weight cycles, then after the Bellman-Ford algorithm executes, d[v] = δ(s, v) for all v ∈ V. Theorem. If G = (V, E) contains no negative- weight cycles, then after the Bellman-Ford algorithm executes, d[v] = δ(s, v) for all v ∈ V. Proof. Let v ∈ V be any vertex, and consider a shortest pathpfromstovwiththeminimumnumberofedges. B 1 0731 2 A 4 3 2 E 4 2 –3 s 6 vvv 22 23 24 –1 B A518E v CD v1 v3 vk C D p:v 1 v 3 ... k 5 vv2 2 −2 02 End of pass 2 (and 3 and 4). Since p is a shortest path, we have δ(s, vi) = δ(s, vi–1) + w(vi–1, vi) . 25 26 27 0 s v vvv Let A be an m×n matrix, b be an m-vector, and c be an n-vector. Find an n-vector x that maximizes cTx subject to Ax ≤ b, or determine that no such solution exists. Correctness (continued) Detection of negative-weight cycles Linear programming v1 v3 vk Corollary. If a value d[v] fails to converge after |V| – 1 passes, there exists a negative-weight cycle in G reachable from s. p:v 1 v 3 ... k v0 v2 02 Initially, d[v0] = 0 = δ(s, v0), and d[v0] is unchanged by subsequent relaxations (because of the lemma from Shortest Paths I that d[v] ≥ δ(s, v)). • After 1 pass through E, we have d[v1] = δ(s, v1). n • After 2 passes through E, we have d[v2] = δ(s, v2). M m maximizing . • After k passes through E, we have d[vk] = δ(s, vk). Since G contains no negative-weight cycles, p is simple. Longest simple path has ≤ |V| – 1 edges. . ≤ Ax≤b cTx Linear-programming algorithms Linear-programming algorithms Solving a system of difference Algorithms for the general problem Algorithms for the general problem Linear programming where each row of A contains exactly one 1, one –1, and the rest 0’s. • Simplex methods — practical, but worst-case exponential time. • Simplex methods — practical, but worst-case exponential time. Example: • Interior-point methods — polynomial time and competes with simplex. • Interior-point methods — polynomial time and competes with simplex. x1 –x2 ≤3 x2 –x3 ≤–2 x1 –x3 ≤2 xj –xi ≤wij Solving a system of difference Solving a system of difference Unsatisfiable constraints constraints constraints Linear programming where each row of A contains exactly one 1, one –1, and the rest 0’s. Linear programming where each row of A contains exactly one 1, one –1, and the rest 0’s. Theorem. If the constraint graph contains a negative-weight cycle, then the system of differences is unsatisfiable. Example: Solution: Example: Solution: x1 – x2 ≤ 3 x2 – x3 ≤ –2 x1 – x3 ≤ 2 xj – xi ≤ wij x1 = 3 x2 = 0 x3 = 2 x1 – x2 ≤ 3 x2 – x3 ≤ –2 x1 – x3 ≤ 2 xj – xi ≤ wij x1 = 3 x2 = 0 x3 = 2 28 29 30 31 32 33 Feasibility problem: No optimization criterion. Just find x such that Ax ≤ b. • In general, just as hard as ordinary LP. Constraint graph: (The “A” matrix has x–x≤w v v dimensions wij j i ij vii vjj |E | × |V |.) 34 35 36 constraints Unsatisfiable constraints Unsatisfiable constraints Satisfying the constraints Theorem. If the constraint graph contains a negative-weight cycle, then the system of differences is unsatisfiable. Proof. Suppose that the negative-weight cycle is v1 →v2 →L→vk →v1. Then,wehave Theorem. If the constraint graph contains a negative-weight cycle, then the system of differences is unsatisfiable. Theorem. Suppose no negative-weight cycle exists in the constraint graph. Then, the constraints are satisfiable. x2 – x1 ≤w12 x2 – x3 – x2 ≤w23 x3 – x1 x2 ≤ w12 ≤ w23 Therefore, no values for the x M M xk – xk–1 ≤wk–1,k xk – x1 – xk ≤wk1 x1 – xk–1 xk ≤wk–1,k ≤ wk1 i Satisfying the constraints Satisfying the constraints Proof (continued) Theorem. Suppose no negative-weight cycle exists in the constraint graph. Then, the constraints are satisfiable. Proof. Add a new vertex s to V with a 0-weight edge toeachvertexv ∈V. Theorem. Suppose no negative-weight cycle exists in the constraint graph. Then, the constraints are satisfiable. Proof. Add a new vertex s to V with a 0-weight edge toeachvertexv ∈V. Claim: The assignment xi = δ(s, vi) solves the constraints. Consider any constraint xj – xi ≤ wij, and consider the shortest paths from s to vj and vi: Bellman-Ford and linear programming Application to VLSI layout compaction VLSI layout compaction Corollary. The Bellman-Ford algorithm can solve a system of m difference constraints on n variables in O(mn) time. Integrated -circuit features: d1 1 Single-source shortest paths is a simple LP problem. minimum separation λ In fact, Bellman-Ford maximizes x1 + x2 + L + xn subjecttotheconstraintsx –x ≤w andx ≤0 (exercise). j i ij i Problem: Compact (in one dimension) the space between the features of a VLSI layout without bringing any features too close together. x x Bellman-Ford also minimizes maxi{xi} – mini{xi} (exercise). Bellman-Ford minimizes maxi{xi} – mini{xi}, v9 v9 99 No negative-weight cycles introduced ⇒ shortest paths exist. vjj The triangle inequality gives us δ(s,vj) ≤ δ(s, vi) + wij. vv v4 sv4 4 4 vv v3 v3 33 Since xi = δ(s, vi) and xj = δ(s, vj), the constraint xj – xi ≤w issatisfied. vv Proof. Suppose that the negative-weight cycle is v1 →v2 →L→vk →v1. Then,wehave 0 ≤ weight of cycle can satisfy the constraints. v7 v7 7 7 ij <0 37 38 39 i i ii vvw v1 v1 1 v 0 1 v Note: δ(s,vj) ij v 40 41 42 which compacts the layout in the x-dimension. 43 44 45 δ(s, v ) s i v 12 Constraint: x2 – x1 ≥ d1 + λ 1 2