La distance n’y fait rien; il n’y a que le premier pas qui coûte.
[The distance is nothing; it is only the ﬁrst step that costs.]— Marie Anne de Vichy-Chamrond, marquise du Deffand,letter to Jean le Rond d’Alembert, July 7, 1763
Tam quaestiones altioris indaginis poscuntur.
[Then these questions require further investigation.]— Carl Gustav Jacob Jacobi, unpublished notes (c. 1836)
Cecil Graham: What is a cynic?
Lord Darlington: A man who knows the price of everything, and the value of nothing.
Cecil Graham: And a sentimentalist, my dear Darlington, is a man who sees an absurd value
in everything and doesn’t know the market price of any single thing.
— Oscar Wilde, Lady Windermere’s Fan, A Play About a Good Woman (1892)

G
Minimum-Cost Flows[Read Chapters 8, 10, 11, and F ﬁrst.]
Status: Text beta. Needs ﬁgures.

In this final chapter on flows, we consider a significant generalization of the maximumflow problem that (as far as we know) cannot be solved by modifying the graph andapplying a standard flow algorithm. The input to our problem consists of a flow network
without special source and target vertices, where each edge e has a cost $(e), in addition
to the usual edge capacities and vertex balances. Edge costs can be positive, negative, orzero. The total cost of any flow f is then defined asX$( f ) =$(e) · f (e).
e∈E

The minimum-cost flow problem asks for a feasible flow with minimum cost, instead ofa feasible flow with maximum value.

G.1

Minimum-Cost Circulations

The simplest special case of the minimum-cost flow problem requires the input flow
network to satisfy two constraints:© 2018 Jeff Erickson

http://algorithms.wtf

1

G. MINIMUM-COST FLOWS• All vertex P
balances are zero.
Thus, every flow f must satisfy the conservation
P
constraint u f (u v) = w f (v w) at every vertex v.

• Edges have non-negative capacities and zero lower bounds. Thus, every feasible
flow f satisfies the capacity constraint 0 ≤ f (u v) ≤ c(u v) at every edge u v.
Because the vertex balances are all zero, any feasible flow in such a network is actually acirculation—a sum of directed cycles. This special case is normally called the minimumcost circulation problem.
The standard maximum-flow problem can be reduced to the minimum-cost circulation
problem as follows. Suppose we are given a flow network G = (V, E) with source andtarget vertices s and t and non-negative edge capacities c(e). Let G 0 = (V, E 0 ) be the
network constructed from G by assigning cost 0 to every edge, and then adding a single
edge t s with infinite capacity and cost −1. Every feasible (s, t)-flow f in G can beextended to a feasible circulation in G 0 by definingXX
f (t s) = | f | =f (sw) −f (us);wumoreover, the cost of the resulting circulation is precisely −| f |. Conversely, for any
feasible circulation f : E 0 → R, the restriction f | E is a feasible (s, t)-flow in G with value− f (t s). Thus, any maximum-value (s, t)-flow in G corresponds to a minimum-cost
circulation in G 0 and vice versa.

ÆÆÆFigure!

Cycle Canceling
We can solve any instance of the minimum-cost circulation problem using a naturalgeneralization of the Ford-Fulkerson augmenting path algorithm called cycle canceling.
This algorithm is normally attributed to Morton Klein in 1967, but the key insights dateback at least to A. N. Tolstoy’s studies of railway transportation networks in the late
1920s.
Consider an arbitrary circulation f in G. As usual, the residual network G f consistsof all edges u v with non-zero residual capacity c f (u v). For each residual edge u v
in G f that is not an edge in the original graph G, we define its cost as follows:$(u v) := −$(v u).

ÆÆÆ

Figure showing ﬂow f and residual graph G f

Now let γ be a directed cycle in the residual graph G f . We define the residual
capacity c f (γ) of γ to be the minimum residual capacity of the edges in γ, and the cost$(γ) of γ to be the sum of the costs of the edges in γ. More concisely:Xc f (γ) := min c f (e)$(γ) :=
$(e)
e∈γ

2

e∈γ

G.1. Minimum-Cost Circulations

Exactly as in Ford-Fulkerson, we can augment the circulation f , by pushing R units offlow around γ, to obtain a new circulation f 0 : f (u v) + c f (γ) if u v ∈ γ
f 0 (u v) =f (u v) − c f (γ) if v u ∈ γ f (u v)otherwise

Straightforward calculation now implies that$( f 0 ) = $( f ) + c f (γ) · $(γ).

In particular, if $(γ) < 0, the new circulation f 0 has lower cost than the original
circulation f . We immediately conclude that a feasible circulation f is a minimumcost circulation if and only if G f contains no negative cycles.
Figure showing negative cycle and updated ﬂow f 0ÆÆÆFinally, Klein’s cycle canceling algorithm initializes f to the all-zero circulation, andthen repeatedly augments f along an arbitrary negative residual cycle, until there are
no more negative residual cycles. For the special instances generated by our reduction
from maximum flow, every negative-cost residual cycle consists of a path from s to t
and the sole negative edge t s, so cycle canceling is equivalent to Ford and Fulkerson’s
augmenting path algorithm.

Analysis
In each iteration of the algorithm, we can find a negative-cost cycle in O(V E) time using
a straightforward modification of the Shimbel-Bellman-Ford shortest path algorithm(hint, hint). If both the capacity and the cost of each edge is an integer, then each cycleaugmentation decreases the cost of the circulation by a positive integer, and therefore
by at least 1. It follows that the cycle canceling algorithm runs in O(V E · |$( f ∗ )|) time,
where f ∗ is the final circulation. The crude bound $( f ∗ ) ≥ −EC K, where C = maxe c(e)and K = maxe |$(e)|, also implies that the algorithm runs in at most O(V E 2 C K ) time.
As one might expect from Ford-Fulkerson, these time bounds are exponential in thecomplexity of the input even when capacities are integers, both time bounds are tight in
the worst case, and the algorithm may not terminate or even approach a minimum-cost
circulation in the limit if any capacities are irrational.1
Like Ford-Fulkerson, more careful choices of which cycle to cancel lead to more
efficient algorithms. Unfortunately, some natural choices are NP-hard to compute,1

If the input network has integer capacities, the algorithm must eventually terminate even when costs
are irrational, because there are only a finite number of feasible integer circulations. However, the numberof iterations could still be exponential, even if we always cancel the cycle with most negative total cost!

3G. MINIMUM-COST FLOWS

including the cycle with the most negative total cost and the negative cycle with thefewest edges. In the late 1980s, Andrew Goldberg and Bob Tarjan developed a minimumcost flow algorithm that repeatedly cancels the so-called minimum-mean cycle, whichis the cycle whose average cost per edge is smallest. By combining an algorithm of Karp
to compute minimum-mean cycles in O(V E) time, efficient dynamic tree data structures,and other sophisticated techniques that are (unfortunately) beyond the scope of thisclass, their algorithm achieves a running time of O(V E 2 log V).

Reduction from General Minimum-Cost Flow
In the standard general formulation of the minimum-cost flow problem, we are given a
directed flow network G = (V, E) with the following additional data:• a capacity function c : E → R such that c(e) ≥ 0 for all e ∈ E;
• a lower bound function `: E → R such that 0 ≤ `(e) ≤ c(e) for all e ∈ E;P
• a balance function b : V → R such that v b(v) = 0; and• a cost function $: E → R.

As usual, a feasible flow in G is a function f : E → R that satisfies the P
capacity constraints
`(e)
≤
f
(e)
≤
c(e)
at
every
edge
e
and
the
balanceconstraintsu f (u v) −Pw f (v  w) = b(v) at every vertex v. The
Pminimum-cost flow problem asks for a feasible
flow f with minimum total cost $( f ) = e $(e) · f (e).
We can solve the general minimum-cost flow problem in two stages. First, find any
feasible flow f in G, by reducing to the maximum-flow problem as described in theprevious chapter. If there is no feasible flow in G, we can immediately report failure.
Otherwise, in the second stage, we compute a minimum-cost circulation f 0 in the residual
graph G f , using (for example) cycle canceling. Tedious definition-chasing implies thatthe function f + f 0 is a minimum-cost flow in the original network G. In total, thisalgorithm runs in O(V E 2 log V) time.

G.2

Successive Shortest Paths

The cycle canceling algorithm implies a natural characterization of minimum-cost flows.
Consider a general flow network G = (V, E) with capacities, lower bounds, costs, andbalances. A pseudoflow ψ: E → R is a minimum-cost flow if and only if it satisfies three
conditions:• Feasible: `(e) ≤ ψ(e) ≤ c(e) for every edge e.
P
P• Balanced: u ψ(u v) − w ψ(v w) = b(v) for every vertex v.

• Locally optimal: The residual graph Gψ contains no negative-cost cycles.

The cycle-canceling algorithm incrementally improves a feasible and balanced pseudoflow(that is, a circulation) until it is also locally optimal. A complementary strategy
called successive shortest paths incrementally improves a feasible and locally optimal
4G.2. Successive Shortest Paths

pseudoflow until it is also balanced. The successive shortest paths algorithm was initially
proposed by Ford and Fulkerson in the mid-1950s, and then later rediscovered by William
Jewell in 1958, Masao Iri in 1960, and Robert Busacker and Paul Gowen in 1960.
The successive shortest paths algorithm requires two simplifying assumptions about
the initial flow network G:• All lower bounds are zero. Otherwise, think of the lower-bound function ` as a
pseudoflow (sending `(e) units of flow across each edge e), and consider the residual
graph G` .
• All costs are non-negative. Otherwise, consider the residual graph of the following
pseudoflow:¨c(u v) if $(u v) ≤ 0c(u v) =0otherwise
Enforcing these assumptions may introduce non-zero balances at the vertices, even if
all balances in the initial flow network are zero. These two assumptions imply that the
all-zero pseudoflow is both feasible and locally optimal, but not necessarily balanced.
The successive shortest path algorithm begins by initializing ψ to the all-zeropseudoflow, and then repeatedly augments ψ by pushing flow along a shortest path in
the residual graph Gψ from any vertex with negative residual balance to any vertex withpositive residual balance, where the length of a path in Gψ is the sum of the residual
costs of its edges. The algorithm is described in more detail below:
SuccessiveShortestPaths(V, E, c, b, $):for every edge e ∈ E
ψ(e) ← 0P
B ← v |b(v)|/2
while B > 0
construct Gψs ← any vertex with bψ (s) < 0t ← any vertex with bψ (t) > 0
σ ← shortest path in Gψ from s to t
Augment(s, t, σ)return ψAugment(s, t, σ):R ← min −bψ (s), bψ (t), mine∈σ cψ (e)B ← B−Rfor every directed edge e ∈ σ
if e ∈ E
ψ(e) ← ψ(e) + R
else 〈〈rev(e) ∈ E〉〉
ψ(e) ← ψ(e) − R(To simplify the pseudocode, I have assumed implicitly that the residual graph Gψ
is always strongly connected. If necessary, this assumption can be enforced by adding
a new vertex with zero balance and with infinite-cost edges to and from every othervertex in G. If SuccessiveShortestPaths ever tries to push flow along one of these
new edges, we can immediately report that the original flow problem is infeasible.)
SuccessiveShortestPaths is obviously an instantiation of the FeasibleFlow
algorithm from the previous chapter; the only difference is that we require eachaugmenting path σ to be a shortest path, instead of an arbitrary path. So obviously the5

G. MINIMUM-COST FLOWS

algorithm either returns a feasible flow (that is, a feasible and balanced pseudoflow) or
reports correctly that no such flow exists.
Unfortunately, like almost(?) every other sentence that uses the words “obviously”,
the previous argument misses a crucial subtlety: Shortest paths are only well-defined ingraphs without negative cycles! To argue that SuccessiveShortestPaths is even awell-defined algorithm, much less a correct algorithm, we need to prove the following
lemma:
Lemma G.1. After every iteration of the main loop of SuccessiveShortestPaths, thefeasible pseudoflow ψ is locally optimal; that is, the residual graph Gψ contains no
negative cycles.
Proof: We prove the lemma by induction. The base case is immediate; the initial all-zeropseudoflow is locally optimal because the graph G has no negative edges.
Suppose that ψ is locally optimal at the beginning of an iteration of the main loop.
By definition, there are no negative cycles in the residual graph Gψ , so shortest paths
are well-defined. Let s be an arbitrary supply vertex and let t be an arbitrary demandvertex in Gψ . Let σ be a shortest path in Gψ , and let ψ0 be the resulting pseudoflow
after augmenting along σ. We need to prove that ψ0 is locally optimal.
For the sake of argument, suppose the residual graph Gψ0 contains a negative cycle γ.
Let f = σ + γ denote the pseudoflow in Gψ obtained by sending one unit of flow along σ
and then one unit of flow along γ. Although γ may contain edges that are not in Gψ ,all such edges must be reversals of edges in σ; thus, f is positive only on edges in Gψ .
Routine calculations imply that f is an integral (s, t)-flow in Gψ with value 1.2 Thus, by
the Flow Decomposition Lemma, f can be decomposed into a single path σ0 from s tot and possibly one or more cycles γ1 , . . . , γk . Our assumption that ψ is locally optimal
implies that each cycle γi has non-negative cost, and therefore $(σ0 ) ≤ $( f ) < $(σ). But
this is impossible, because σ is a shortest path from s to t.
ÆÆÆ

Figure with a complicated instance of σ and γ.

For the special instances of minimum-cost flow generated by our reduction frommaximum flow, the only supply node is the source vertex s, the only deficit node is thetarget vertex t, and every edge in the network has cost 0 except the edge s t, which
has cost 1. Thus, for these instances, the successive shortest paths is equivalent to Fordand Fulkerson’s augmenting path algorithm (followed by a single augmentation of theedge s t).
2
Here I’m ignoring the residual balances in Gψ . Note that f may not be a feasible flow in Gψ , but that
doesn’t matter.

6

G.3. Node Potentials and Reduced Costs

Analysis
In each iteration of the algorithm, we can find a shortest in O(V E) time using a the
Shimbel-Bellman-Ford shortest path algorithm. (Actually, we can use Dijkstra’s algorithm
to compute the first shortest path, but augmenting along a path of positive-cost edges
introduces residual edges with negative costs, so we can’t use Dijkstra’s algorithm inlater iterations.)
Assuming the capacity of each edge is an integer, then each augmentation decreases
the total absolute balance B by a positive integer, and therefore by at least 1. It follows
that the cycle canceling algorithm halts after at most B iterations and thus runs inO(V E B) time. As one might expect from Ford-Fulkerson, this time bound is exponential
in the complexity of the input when capacities are integers, the time bound are tight in
the worst case, and the algorithm may not terminate or even approach a minimum-cost
circulation in the limit if any capacities are irrational.

G.3

Node Potentials and Reduced Costs

The main bottleneck in Ford and Fulkerson’s successive shortest paths algorithm iscomputing a shortest paths in every iteration. Because some edges in the residual
graph may have negative costs, we are forced to use Bellman-Ford instead of Dijkstra’salgorithm. Or so it seems.
The following clever trick to speed up successive shortest paths was proposed byJack Edmonds and Richard Karp in 1969 (published in 1972) and independently byNobuaki Tomizawa in 1970 (published in 1971). The same trick was later applied by
Donald Johnson in the late 1970s to speed up all-pairs shortest-path algorithms; Johnson
attributes the trick to Edmonds and Karp.
Suppose each vertex v in the flow network has been assigned an arbitrary realpotential π(v ). We define the reduced cost of each edge with respect to potentialfunction π as follows:$π (u  v) := π(u) + $(u v) − π(v).
Then for any path α from u to v, we immediately haveXX
$π (α) =$π (e) = π(u) +$(e) − π(v) = π(u) + $(α) − π(v).
e∈α

e∈α

The potentials of all the intermediate vertices on α cancel out; intuitively, for eachintermediate vertex x, we get an “entrance gift” of π(x) when the path enters x, which
we immediately pay back as an “exit tax” when the path leaves x. This simple observation
has two important consequences:• Shortest paths with respect to the reduced cost function $π are identical to shortest
paths with respect to the original cost function $.
7

G. MINIMUM-COST FLOWS• For any cycle γ, we immediately have $π (γ) = $(γ); thus, a flow network G has no
cycles with negative cost if and only if G has no cycles with negative reduced cost.
Edmonds, Karp, and Tomizawa observed that if we choose the right potential function,
we can ensure that all reduced edge costs are non-negative, allowing us to computeshortest paths using Dijkstra’s algorithm instead of Bellman-Ford.
Lemma G.2. A flow network G has no negative-cost cycles if and only if, for somepotential function π: V → R, every edge in G has non-negative reduced cost.
Proof: One direction is easy. Suppose G contains a cycle γ with negative cost. Then forevery potential function π, we have $π (γ) = $(γ) < 0, which implies that at least oneedge in γ has negative reduced cost.
Conversely, suppose G has no negative-cost cycles. Then shortest path distances withrespect to the cost function $ are well-defined. Fix an arbitrary vertex s, and for every
vertex v, let dist(v) denote the shortest-path distance from s to v. (If necessary, add
zero-capacity, high-cost edges from s to every other vertex, so that these distances are all
finite.) Then for every edge u v, we immediately havedist(v) ≤ dist(u) + $(u v),
since otherwise there would be a path from s through u to v with cost less than dist(v);this inequality can be rewritten as
dist(u) + $(u v) − dist(v) ≥ 0.
Thus, if use these shortest-path distances as potentials, every edge in G has non-negative
reduced cost.


Speeding up Successive Shortest Paths
Now we seem to have a chicken-and-egg problem: We need a good potential function tocompute shortest paths quickly, but we need shortest paths to compute a good potentialfunction!
We can break this apparent cycle as follows. Because the original flow network G
has only non-negative edge costs, we can start with π(v) = 0 at every vertex v. Thenafter each iteration of the main loop, we update the vertex potentials to ensure that
reduced costs in the new residual graph are still non-negative. Specifically, we use
the shortest-path distances from each iteration as the vertex potentials in the next
iteration, as described in the pseudocode below.
8G.3. Node Potentials and Reduced Costs

FastSuccessiveShortestPaths(V, E, c, b, $):for each edge e ∈ E
ψ(e) ← 0for each vertex v ∈ V
π(e) ← 0P
B ← v |b(v)|/2
while B > 0
construct Gψs ← any vertex with bψ (s) < 0t ← any vertex with bψ (t) > 0
dist ← Disjkstra(Gψ , s, $π )σ ← shortest path in Gψ from s to t 〈〈computed in the previous line〉〉
Augment(s, t, σ)
for each vertex v ∈ V
π(v) ← dist(v)return ψ

Lemma G.3. After every iteration of the main loop of FastSuccessiveShortestPaths,
every edge u v in the residual graph Gψ has non-negative reduced cost: $π (u v) ≥ 0.
Proof: We prove the lemma by induction. The base case is immediate, because theoriginal graph G has no negative-cost edges.
Suppose at the beginning of some iteration that for every edge u v in Gψ , we have$π (u v) ≥ 0. Let s be an arbitrary supply vertex, and for any vertex v, let dist(v) denotethe shortest-path distance from s to v with respect to the reduced cost function $π . Let σ
be a shortest path in Gψ from s to some demand vertex t, and let ψ0 be the resulting
pseudoflow after augmenting along σ.
Now let u v be an arbitrary edge in the new residual graph Gψ0 . We need to provethat $dist (u v) ≥ 0. There are two cases to consider:• Suppose u v is an edge in the old residual graph Gψ . Then following the proof of
Lemma 2, we immediately have $dist (u v) = dist(u) + $π (u v) − dist(v) ≥ 0.

• Suppose u v is not an edge in the old residual graph Gψ . Then u v must be thereversal of an edge in σ. It follows that dist(u) = dist(v) + $π (v u), and therefore$dist (u v) := dist(u) + $π (u v) − dist(v)= dist(u) + π(u) + $(u v) − π(v) − dist(v)= dist(u) + π(u) − $(v u) − π(v) − dist(v)= dist(u) − $π (v u) − dist(v)= 0.

In both cases, we conclude that $dist (u v) ≥ 0, as required.


9

G. MINIMUM-COST FLOWSThis lemma implies that we can compute shortest paths at every iteration of FastSuccessiveShortestPaths using Disjktra’s algorithm in O(E log V ) time. It follows
that the overall algorithm runs in O(BE log V) time.
The fastest minimum-cost flow algorithm currently known (at least among algorithms
whose running times depend only on V and E), due to James Orlin in the early 1990s,
reduces the problem to O(E log V ) iterations of Dijkstra’s shortest-path algorithm andtherefore runs in O(E 2 log2 V) time.

G.4

Transshipment and Transportation

The transshipment and transportation problems are two interesting special cases ofminimum-cost flows, where the flow values are not directly limited by capacity constraints
on the edges, but rather indirectly limited by the balance conditions at the vertices.
A transshipment network is a directed graph G = (V, E) with vertex balancesb : V → R and edge costs $: E → R, but no capacity function; each edge is allowed tocarry any non-negative amount of flow. Thus, a feasible P
flow in such a network
is a functionP
f : E → R such that f (e) ≥ 0 for every edge e and u f (u v) − w f (v w) = b(v)for every vertex v. As usual,
Pthe transshipment problem asks for a feasible flow withminimum total cost $( f ) = e $(e) · f (e).
The transshipment problem was first cast in this discrete form by Alex Orden in 1956.
However, transshipment has been a common practice in long-distance commerce for as
long as there has been long-distance commerce.
Traditionally, the vertices in a transshipment network are divided into three categories:
supply or source vertices have negative balance; demand or target vertices have positivebalance, and transshipment vertices have zero balance. The transportation problem is a
special case of the transshipment problem in which the input satisfies two additional
conditions:• There are no transshipment nodes; every vertex has a non-zero balance constraint.
• Every edge u v leaves a supply node u and enters a demand node v. Thus, the flow
network is a directed bipartite graph, where the vertex partition separates supply
vertices from demand vertices.
Some formulations of the transportation problem require G to be a complete bipartite
graph, but if necessary we can introduce any missing edges with infinite cost.
The transportation problem was first cast in this modern form by Frank Hitchcockin 1942 and independently by Tjalling Koopmans in 1947; however, earlier versions of
the problem were studied by Leonid Kantorivich in the late 1930s, A. N. Tolstoy in the
1920s and 1930s, and even earlier (as a continuous mass-transport problem) by Gaspard
Monge in the late 1700s.

10G.4. Transshipment and Transportation

Reducing Minimum-Cost Flow to Transportation
Like the minimum-cost circulation problem, is is possible to reduce arbitrary instancesof minimum-cost flow to the transportation problem; the following reduction was
described by Delbert Fulkerson in 1960, generalizing Orden’s 1956 reduction from thetransshipment problem. Let G = (V, E) be an arbitrary flow network, where every edgee has an associated lower bound `(e), capacity c(e), and cost $(e), and every vertex v
has an associated balance b(v).
We can remove the capacity constraints from any single edge u v as follows. First,
replace the edge with a pair of edges uzuv and v zuv , where zuv is a new vertex. Next,
set the various constraints for the new vertex and edges as follows:• `(uzuv ) = `(v zuv ) = 0,
• c(uzuv ) = c(v zuv ) = ∞,• $(uzuv ) = $(u v) and $(v zuv ) = 0, and• b(zuv ) = c(u v) − `(u v);
Finally, increase the balance b(u) by `(u v) and decrease the balance b(v) by c(u v).
Call the resulting flow network G 0 .
` f c

b

b+`

b0

$

0 f

$

`1

c

`

0c

f 1

0

b0

c

Removing capacity constraints from a single edge.

Given any feasible flow f in the original network G, we can construct a corresponding
flow f 0 in G 0 by setting f (u v) − `(u v) if e = uzuv ,0f (e) = c(u v) − f (u v) if e = v zuv , f (e)otherwise.
Routine calculations imply that f 0 is a feasible flow in G 0 with cost $( f )−`(u v)·$(u v).
Conversely, given a feasible flow f 0 in G 0 , we can construct a corresponding flow f in G
by setting¨
f 0 (uzuv ) + `(u v) if e = u v,
f (e) =
f 0 (e)otherwise.
Again, routine calculations imply that f is a feasible flow in G with cost $( f ) + `(u v) ·$(u v). We conclude, for both flow transformations, that f is a minimum-cost flow in G
if and only if f 0 is a minimum cost flow in G 0 .
11

G. MINIMUM-COST FLOWS

Applying this transformation to every edge in G, we obtain a bipartite transportation
network H with V + E vertices and 2E uncapacitated edges in O(E) time. Given aminimum-cost flow in H, we can easily recover a minimum-cost flow in the original
network G in O(E) time.

Special case: Assignment
We conclude by describing two further interesting special cases of the transshipment/transportation problem.
The assignment problem is a special case of the Hitchcock-Koopman’s transportation
problem in which every supply vertex has balance −1 and every demand vertex hasbalance +1. In other words, the assignment problem asks for a minimum-weight
perfect matching in a bipartite graph with weighted edges (where “weight” is what
we previously called “cost”). The assignment problem can also be reformulated as a
maximum-weight perfect matching problem by negating all edge weights.
The assignment problem was first posed and solved by the German mathematician
Carl Jacobi in the early 1800s, motivated by the problem of solving a system of ordinary
differential equations. Jacobi’s algorithm was not published until after his death.3
Jacobi’s algorithm was rediscovered by Harold Kuhn in the mid 1950s. Kuhn called hisalgorithm the “Hungarian method”, because its relied on combinatorial results on perfectmatchings published by Hungarian mathematicians Dénes Kőnig and Jenő Egerváry in
1931. (Alas, Jacobi was not Hungarian.) In 1957, topologist James Munkres observed that
the Jacobi-Egerváry-Kuhn algorithm runs in O(V 4 ) time; with more care, the running
time can be improved to O(V 3 ).
Any instance of the transportation problem with integer balances can be transformed
into an equivalent instance of the assignment problem, by replacing each vertex v with|b(v)| equivalent copies.

Special Case: Single-Supply Transshipment
Perhaps the most important special case of the transhipment problem requires thatthe network has exactly one supply node s. This special case is better known as the
single-source shortest path problem. Specifically, let T be a shortest-path tree of G
rooted at the supply vertex s, and let dist(v) denote the shortest-path distance from s
to v. We define a canonical flow f T : E → R for this spanning tree as follows:f T (u v) =3

¨P0w↓v b(w)

if u v ∈ Totherwise

Carl Gustav Jacob Jacobi. De investigando ordine systematis aequationum differentialum vulgarium
cujuscunque. J. Reine Angew. Math. 64(4):297–320, 1865. Posthumously published by Carl Borchardt.
English translation by François Ollivier: Looking for the order of a system of arbitrary ordinary differential
equations. Applicable Algebra in Engineering, Communication and Computing, 20(1):7–32, 2009.

12

Exercises(Here w ↓ v indicates that w is a descendant of v in T .) Equivalently, f t ) is the sum of
V − 1 path flows, each sending b(v) units of flow along the unique path from s to someother vertex v; thus,X$( f T ) =dist(v) · b(v).
v

We can prove this canonical flow is optimal in (at least) two different ways. First, f T is
precisely the minimum-cost flow constructed by the successive shortest-path algorithm(at least if the shortest path tree T is unique). Second, following the proof of Lemma 1,
if the residual graph G f T contained any negative cycles, we could find a shorter pathfrom s to some other vertex v.
Ford’s generic relaxation algorithm to compute shortest path trees is morally equivalent to cycle canceling. Ford’s algorithm maintains a tentative shortest path tree T . Any
tense edge u v indicates a negative cycle in the residual graph G T = G f T , consisting ofu v and the unique path from v to u in T . Relaxing u v replaces the unique edge x  v
in T with u v.
In fact, for every transhipment network G without negative cycles, there is anminimum-cost flow is non-zero only on the edges of some spanning tree of G.

ExercisesÆÆÆNeed more!

1. Describe and analyze an algorithm for the following problem, first posed and solvedby the German mathematician Carl Jacobi in the early 1800s.
(i)

Disponantur nn quantitates hk quaecunque in schema Quadrati, ita ut k habeanturn series horizontales et n series verticales, quarum quaeque est n terminorum. Ex
illis quantitatibus eligantur n transversales, i.e. in seriebus horizontalibus simul
atque verticalibus diversis positae, quod fieri potest 1.2 . . . n modis; ex omnibus
illis modis quaerendum est is, qui summam n numerorum electorum suppeditet
maximam.

For the tiny minority of students who are not fluent in mid-19th century academic
Latin, here is a modern English formulation of Jacobi’s problem. Suppose we are
given an n × n matrix M . Describe and
Pnanalyze an algorithm that computes a
permutation σ that maximizes the sum i=1 Mi,σ(i) , or equivalently, permutes thecolumns of M so that the sum of the elements along the diagonal is as large as
possible.
Please write a complete, self-contained solution in English, not in mid-19th
century academic Latin. Or Hungarian.
2. An (s , t )-series-parallel graph is an directed acyclic graph with two designatedvertices s (the source) and t (the target or sink) and with one of the following
structures:
13

G. MINIMUM-COST FLOWS• Base case: A single directed edge from s to t.
• Series: The union of an (s, u)-series-parallel graph and a (u, t)-series-parallelgraph that share a common vertex u but no other vertices or edges.
• Parallel: The union of two smaller (s, t)-series-parallel graphs with the same
source s and target t, but with no other vertices or edges in common.
Recall that any series-parallel graph can be represented by a binary decomposition tree,
whose interior nodes correspond to series compositions and parallel compositions,and whose leaves correspond to individual edges. The decomposition tree can beconstructed in O(V + E) time.
(a) Describe an efficient algorithm to compute a minimum-cost maximum flow from s
to t in an (s, t)-series-parallel graph whose edges have unit capacity and arbitrary
costs.
ª(b) Describe an efficient algorithm to compute a minimum-cost maximum flow from s
to t in an (s, t)-series-parallel graph whose edges have arbitrary capacities andcosts.

3. Every year, Professor Dumbledore assigns the instructors at Hogwarts to various
faculty committees. There are n faculty members and c committees. Each committee
member has submitted a list of their prices for serving on each committee; each pricecould be positive, negative, zero, or even infinite. For example, Professor Snapemight declare that he would serve on the Student Recruiting Committee for 1000
Galleons, that he would pay 10000 Galleons to serve on the Defense Against the
Dark Arts Course Revision Committee, and that he would not serve on the Muggle
Relations committee for any price.
Conversely, Dumbledore knows how many instructors are needed for eachcommittee, as well as a list of instructors who would be suitable members for eachcommittee. (For example: “Dark Arts Revision: 5 members, anyone but Snape.”) If
Dumbledore assigns an instructor to a committee, he must pay that instructor’s pricefrom the Hogwarts treasury.
Dumbledore needs to assign instructors to committees so that (1) each committee
is full, (3) no instructor is assigned to more than three committees, (2) only suitable
and willing instructors are assigned to each committee, and (4) the total cost of
the assignment is as small as possible. Describe and analyze an efficient algorithm
that either solves Dumbledore’s problem, or correctly reports that there is no valid
assignment whose total cost is finite.
4. Vince wants to borrow a certain amount of money from his friends as cheaply as
possible, possibly after first arranging a sequence of intermediate loans. Each ofVince’s friends have a different amount of money that they can lend (possibly zero).
For any two people x and y, there is a maximum amount of money (possibly zero
14

Exercises

or infinite) that x is willing to lend to y and a certain profit (possibly zero or evennegative) that x expects from any loan to y.
For example, suppose Vince wants to borrow $100 from his friends Ben andNaomi, who have the following constraints:• Ben has $500 available to lend.
• Ben is willing to lend up to $150 to Vince at a profit of 20¢ per dollar.
• Ben is willing to lend up to $50 to Naomi, at a loss of 10¢ per dollar.
• Naomi has $50 available to lend.
• Naomi is willing to lend any amount of money to Vince, at a profit of 10¢ per
dollar.
• Naomi is not willing to lend money to Ben.
If Vince borrows $100 directly from Ben, he needs $120 to pay off the loan. If
Vince borrows $50 from Ben and $50 from Naomi, he needs $115 to pay off the loan:$60 for Ben and $55 for Naomi. But if Vince asks Naomi to borrow $50 from Ben andthen borrows the entire $100 from Naomi, then he needs only $110 to pay off Naomi,
who can then pay off Ben with just $45. With the same constraints, the maximum
amount of money that Vince can borrow is $250.
Describe and analyze an algorithm that finds a sequence of loans that minimizes
the amount Vince needs to pay everyone off, or correctly reports that Vince cannot
borrow his desired amount. The input has the following components:• An array Money[1 .. n], where Money[i] is the amount of money that friend i has.
• An array MaxLoan[1 .. n, 0 .. n], where MaxLoan[i, j] is the amount of money thatfriend i is willing to lend to friend j. “Friend 0” is Vince.
• An array Profit[1 .. n, 0 .. n], where Profit[i, j] is the profit per dollar that friend i
expects from any load to friend j. Again, “friend 0” is Vince.
• The total amount T that Vince wants to borrow.
5. Suppose you are given a directed flow network G, in which every edge has an integercapacity and an integer cost, and each vertex has an integer balance, along with an
integer minimum-cost flow f ∗ in G. Describe algorithm for the following problems:(a) IncCost(u v): Increase the cost of u v by 1 and update the minimum-cost
flow.
(b) DecCost(u v): Decrease the cost of u v by 1 and update the minimum-cost
flow.
Both algorithms should modify f ∗ so that it is still a minimum-cost flow, more quickly
than recomputing a minimum-cost flow from scratch.

© 2018 Jeff Erickson

http://algorithms.wtf

15