Tämän viikon tehtävien aiheena on maksimivirtaus, ja tehtäviin tarvittava teoria on Tirakirjan luvussa 14.

Ford-Fulkersonin algoritmi

Ford-Fulkersonin algoritmi on tavallisin menetelmä maksimivirtauksen etsimiseen, ja voit käyttää sitä kaikissa tämän viikon tehtävissä.

Algoritmi muodostuu kierroksista, joista jokainen etsii polun alkusolmusta loppusolmuun ja lisää sen avulla virtausta verkkoon. Sinänsä mikä tahansa virtausta lisäävä polku kelpaa, mutta polun valintatapa vaikuttaa algoritmin tehokkuuteen.

Tirakirjassa esitelty toteutus tunnetaan nimellä Edmonds-Karpin algoritmi. Siinä polku valitaan etsimällä leveyshaulla vähiten kaaria sisältävä polku, mikä takaa, että algoritmi toimii tehokkaasti. Tämä menetelmä toimii myös tällä kurssilla, mutta toteutus on hieman ikävä leveyshaun takia.

Vaihtoehtoinen tehokas tapa, joka esiintyy viikon malliratkaisuissa, on skaalaava algoritmi, joka etsii polun, jonka pienin kapasiteetti yltää tiettyyn kynnysarvoon z. Jos tällaista polkua ei löydy, algoritmi puolittaa z:n ja toistaa samaa. Tällöin polun voi etsiä syvyyshaulla, ja toteutus on silti tehokas.

Maksimivirtauksen käyttämisessä kyse on ennen kaikkea siitä, kuinka onnistua palauttamaan erilaisia ongelmia maksimivirtaukseen. Tällöin varsinaista maksimivirtauksen etsivää koodia voi käyttää mustana laatikkona, ja muun koodin määrä voi olla melko pieni.