Munich Personal RePEc Archive

Algoritmi di flusso massimo al minimo costo

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

[img]
Preview
PDF
MPRA_paper_39759.pdf

Download (562kB) | Preview

Abstract

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".

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