9 Kostenminimale Flüsse

Gegeben: G = (V,E) gerichtet, s , t $\in$ V Quelle bzw. Senke. Jeder Kante in G wird eine Kapazität und die Kosten pro Flußeinheit zugeordnet:

$$\begin{array} {l} c: E \to \mathbb {N} ~(\textrm{Kapazit\uml {a}t})\ a: E \to \mathbb {N} ~(\textrm{Kosten})\end{array}$$

Gesucht: der Fluß f der Größe v mit minimalen Kosten.

Idee: Finde zunächst -- z.B. mit Ford/Fulkerson -- irgendeinen Fluß der Größe v . Lenke diesen Fluß nun so um, daß seine Größe gleich bleibt aber seine Kosten sinken.