Munich Personal RePEc Archive

Algoritmi di flusso massimo al minimo costo

Parrini, Alessandro (2009): Algoritmi di flusso massimo al minimo costo.


Download (562kB) | Preview


This work concerns the maximum flows – minimum cost problem and its main algorithmic solutions. Such a problem involves determining the least cost shipment of a commodity through a capacitated network in order to satisfy demands at certain vertices using supplies available at other vertices. It generalizes both the shortest path problem and the maximum flow problem. The search for this particular flow can be obtained by interfacing the "maximum flow algorithm" (by Ford & Fulkerson) with a "shortest path algorithm" (we choose the one by Dijkstra): this will lead to two new algorithms: the "cycle-canceling algorithm" and "successive shortest path algorithm".

MPRA is a RePEc service hosted by
the Munich University Library in Germany.