Algoritmen voor networkflow

Abstract

Hoeveel verkeer kan er passeren doorheen een drukke stad tijdens de spitsuren? Hoeveel olie kan er doorheen een gegeven netwerk van pijpleidingen stromen op een dag? Hoe kan een fruitboer uit Spanje zoveel mogelijk ton sinaasappelen verzenden per vrachtwagen vanuit zijn bedrijf via doorgeefluiken naar verscheidene andere bedrijven in bijvoorbeeld Rusland en dit binnen één week tijd? Elk van deze vragen komt neer op het probleem om zoveel mogelijk artikelen, grondstoffen, producten, ... van het ene station naar het andere binnen een gegeven tijd en eventueel langs allerlei tussenstations te sturen of te laten stromen. Al de stations samen vormen een netwerk met een begin- en eindstation. Er loopt hierbij een hoeveelheid stroom per tijdseenheid van het beginstation naar het eindstation. De hoeveelheid stroom per tijdseenheid doorheen het netwerk wordt begrensd door de capaciteiten van de verbindingen die het netwerk zelf bepalen. Het gestelde probleem oplossen, komt er dus op neer om de