Tietorakenteet
Harjoitustyö TK00TM1

Vesijohtojärjestelmä

Kuvittele, että haluat johtaa mahdollisimman paljon vettä paikasta A paikkaan B monimutkaista putkistoa pitkin. Kullakin putkella on maksimikapasiteettinsa, joka ilmoittaa kuinka paljon vettä ko. putkea pitkin voi mennä. Putkiston voi kuvata suunnatuksi syklittömäksi verkoksi, jossa putkea kuvaa kaari ja putken kapasiteettia kaaren paino. Kaikki solmut täytyy olla saavutettavissa lähtösolmusta (paikka A) ja kaikista solmuista tulee päästä maalisolmuun (paikka B).

Ongelmana on siis ratkaista kuinka paljon vettä tietyn vesijohtoverkon läpi vettä voi maksimissaan virrata. Toteuta Edmonds-Karp algoritmi joka ratkaisee ongelman. Ohjelmasi tulee myös luoda järkeviä satunnaisia suunnattuja syklittömiä verkkoja, jotka toteuttavat edellä mainitut ehdot. Tulosta koko verkon tila kun olet löytänyt maksimaalisen virtauksen.

Viite:
Cormen, T., Leiserson, E., Rivest, R., Introduction to Algorithms. The MIT Press, 1990, 587-600.