Primal-DualAlgorithmExamples(原始对偶算法的例子).pdf

Primal-Dual Algorithm Examples We just saw the general primal-dual algorithm schema. We will now see how to apply it to the Shortest Path Problem and the Max Flow Problem 1 The Shortest Path Problem Given G = (V, E), let A be its (|V | − 1) × |E | node- arc incidence matrix (with the row for t erased since it is redundant). Primal for shortest path problem is ′ min c f   ←− Row s +1  0  Af =    .  .  .  0 f ≥ 0 max πs Dual is πi − πj ≤ cij ∀ (i, j ) ∈ E πi ≷ 0 ∀i πt = 0 Note that πt = 0 must be added in for consistency; in this case πt is a constant and not a variable. 2 Dual max πs πi − πj ≤ cij (i, j ) ∈ E πi ≷ 0 πt = 0 J = {(i, j ) ∈ E : πi − πj = cij } D ⇒ RP Restricted primal (RP) min ξ = m−1 xa i=1 i  +1   0    Af + xa =