Gegeben: G = (V,E) gerichtet, s , t V Quelle bzw. Senke. Jeder Kante in G wird eine Kapazität und die Kosten pro Flußeinheit zugeordnet:
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.