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