3.3. 3.3. Algoritmus a minimális út - maximális potenciál feladatpár megoldására

A bizonyításból kiolvasható, hogy a megoldás útkeresések sorozatából áll. Utat pedig azon éleken kell keresni, amelyeken . Az algoritmus megszervezhető úgy, hogy lépésenként nem számítjuk ki a potenciálrendszert, hanem az élekre számított értékekkel dolgozunk, amelyet az alábbiak szerint definiálunk:

Tehát a hálózat típusú élein kell utat keresni. Az számítása is könnyen megvalósítható a már megismert lefedéssel. A keletkező vágást az táblázat lefedésével szemléltetjük. A vágás definiciójánál ismertetett fedővonalrendszer megalkotásából tudjuk, hogy a fedetlen cellák az vágásbeli élek halmazát, a kétszer fedett cellák a élhalmazt, míg az egyszer fedett cellák az és a élhalmazokat jelölik ki.

Tehát a fedetlen értékek minimuma lesz az érték.

Ahelyett tehát, hogy új potenciálokat számolnánk, azonnal új értékeket határozunk meg, hisz a következő útkeresést ezen táblázaton kell elvégezni. A FORD tétel bizonyításából könnyen kiolvasható az új táblázat számítása, amely a következő:

Az algoritmus kiinduló lépése egy potenciálrendszer megválasztása. A gyakorlatban legtöbbször a kezdeti potenciálrendszert választjuk, így induláskor . A FORD tételből kiolvasható, hogy az algoritmus akkor fejeződik be, ha találunk utat, ez az út lesz a minimális út. Amennyiben a duál változók optimális értékére is kiváncsiak vagyunk, egy kis számolással azokat is megkaphatjuk az utolsó táblázatból. Célszerű az út éleire felírt egyenletekből számolni, hisz itt . Ekkor megkapjuk az uton lévő pontok potenciáljait, a többi pont potenciálját olyan élre írt egyenletből kell meghatározni, amely élen az egyik pont potenciálja ismert. A potenciál meghatározást számpéldán fogjuk bemutatni.