水道管に見立てた有向グラフがあって、 各辺には「頂点 $u$ から $v$ まで水を上限 $cap$ リットル流せる。1リットル流すには $cost$ 円かかる」という $(u,v,cap,cost)$ が決まっている。
$S$ から $T$ まで $F$ リットルの水を流したいとき、最小コスト $C$ はいくら？
辺上の数字の意味: --cap/cost→ Ⓢ--3/3→○--2/1→○ F=5 を流したい場合、 │ │ │ →→↓と流す量が 2、コスト (3+1+2) x 2 = 12 10/5 8/6 10/2 →↓→と流す量が 1、コスト (3+6+9) x 1 = 18 ↓ ↓ ↓ ↓→→と流す量が 2、コスト (5+5+9) x 2 = 38 ○--5/5→○--6/9→Ⓣ 計68のコストがかかる
いろいろあるが、シンプルな解法の1つに最短路反復がある。
グラフの作り方自体は最大流とよく似ている。
グラフを構築したら、最小コストを調べる。
このようにグラフを更新すると、「一旦流してみたけど、このパスをフルに使うと既定流量 $F$ 流せなくなることが後からわかったので一部流さなかったことにする」ことが表現できる。
1～3.の処理を $F=0$ になるまで繰り返すと、その時の $C$ が答え。
計算量は $O(FE \log{V})$、$F$ が流したい流量、$E,V$ がそれぞれグラフの辺数、頂点数。
見つかったパスに流せる流量 $f$ が毎回 $1$ など少ない値だけ、なんてことも理論上はありうるので、$F$ が計算量にかかってくる。
上記では大まかな流れを書いたが、いろいろ問題を最小費用流に当てはめるにあたって例外的な工夫というか、留意すべき点がある。
最小費用のパスを1つ見つけ流せるだけ流す、というアルゴリズムでは、辺の容量が非整数（特に無理数）だと、いつまでたっても増加路がなくならないグラフが作れてしまう。
$cost$ と $-cost$ の辺が同時に張られるため、グラフに負の辺は必ず存在する。
そんなグラフ上で最短経路を探索する必要がある。
何が困るかってDijkstraが使えなくなる。方法は主に2つある。
ポテンシャルは、最短経路探索を複数回行う際に、負辺を上手いこと解消する方法。
（逆辺を除いた）最初のグラフに負辺が含まれなければ、最初の1回は普通にDijkstraを回せる。
Dijkstraで $S$ からの各頂点に対するコストをまず求める。これをポテンシャルとする。（頂点 $v$ のポテンシャルを $h_v$ とする）
2回目以降の経路探索から負辺が生じうるが、以下のようにコストを更新していく。
こうするとあら不思議、負のコストが生じなくなった上で、最短路も正しく求まる。
頂点 $v$ のポテンシャル $h_v$ は1回のDijkstraごとに以下で更新できる。$dist_v$ はポテンシャルを含んだ値。
通常の最短経路探索なら途中で $T$ までたどり着いたらそこで打ち切ればよいが、 今回はポテンシャルの更新があるので、全頂点への距離が求まるまで（キューが空になるまで）流しきる必要がある。
どう対処するかは問題に依るが、経路探索が終わるたびに $S→T$ パスが存在するかチェックする必要がある。
ポテンシャルを導入すればDijkstraが使える、という話をしたが、
最初の1回目の経路探索は何らかの方法で求める必要がある。
最初から負辺があるとここで困る。
解消方法が複数ある。
大体、こんな感じのフローチャートで選択すればいいか。
負辺が含まれていても $S$ から各頂点への最短コストを求めたい。以下のいずれかを使う。
ただし負閉路がある場合は上手くいかないので、別の方法を考える。
各辺に何らかの値を足してコストを正にする→最小費用流を求める→最後に答えから一定値を引く。
たとえば「どの $S→T$ 経路も、使われる辺数が $P$ 本と決まっている」場合、 全ての辺に固定値 $X$ を足して負辺を無くして、最後に答えから $F \times X \times P$ を引けばよい。
他にも上手くいく場合があるが、問題依存で、なかなか一般的な手続きが見つけづらい。
大まかには、負のコストというのはいわば「賞金」なので、 最初にもらえるだけもらったと仮定した後、 それをもらえなくなる行動（を表す辺）を「罰金」＝正のコストとする、と考える場合が多い。
少し最小費用流の捉え方を変化させる。
$S→T$ に水を流すといっても、別に始点・終点が複数あってもよく、以下のように考えることも出来る。
この場合、仮想的な頂点 $S,T$ を追加し、
とすると、単一始点・単一終点の元の問題にできる。
これを踏まえた上で、$cost$ が負である辺 $(u,v,cap,cost)$ があった場合、これを機械的に正の辺にするには、
と上手くいく。
問題が複雑なときに有効な方法だが、 最小費用流の計算量には流量 $F$ がかかってくるのに対し、この方法は $F$ が大きく増加しうる点に注意。
流量が大きいような最大流問題を解くのに、「cost scaling」「容量スケーリング」という手法がある？
辺 $i$ に流す流量によってコストが変化する場合。
などが決まっているとする。
この時、「$x \lt y$ において $cost_{i,x} \le cost_{i,y}$」、
つまり少なく流す分ほどコストが小さい、という条件下で最小費用流のグラフに落とし込める。
（通常はまとめ買いほど安くなるので感覚的には逆だが）
同じ頂点間に辺を複数本張る。
コストの少ない方から使われるので、問題なく答えが求められる。
辺だけで無く、頂点にも容量やコストが定まっている場合、頂点を2倍にすればよい。
↘ ↗
... →ⓥ→ ... ⓥを通過できる容量は全体で10
↗ ⓥを通過した際のコストは1単位あたり6
↘ ↗
... →v1→v2→ ... v1-v2間の辺に、
↗ その容量とコストを当てはめる
（本来のグラフでの）辺を張るとき、vに入る辺はv1に、vから出る辺はv2に接続する。
最大流問題を解くDinic法でも繰り返し $S→T$ パスを見つけるのだが、
BFS → DFSを繰り返す → Tに至る経路が無くなったらBFSでレベル再計算 → DFSを繰り返す…
として、計算量を減らしている。
しかし、最大流が「何でも良いから $S→T$ パスが見つかればいい」のに対し、 最小費用流はコストが最小のものを見つけないといけないので、似たような手法は使えず、1回毎に経路探索を行う必要がある。
最小費用流は「線形計画問題」にとっての代表例らしく、“最小費用流” で検索するとセットでよく出てくる。
最小費用流では、各辺に流す流量を変数として定式化することができる。
これで定式化すると、シンプレックス法（単体法）と呼ばれる方法で、 「ほとんどの場合は高速だけど、ごく稀に指数時間かかる」ような計算量で解けるらしい。