DSC00319 (7)

11.1.1. Algorytm wyznaczania maksymalnego przepływu

Dane

Siei

S-<<M«},{h)>;

g - <iv; c/>		■ <1P,	TH
	1	dla x	» J
a (x) *	0	dla x	e^4 s
	-1	dla .v	■ t

0 < h (x, y) < oo

Procedu ta

|| Przyjmujemy dowolny przepływ (np. zerowy/a 0).

2.    Cechujemy źródło ś cechą (- , oof.    v

Każda cecha wierzchołka x będzie dwuczęściowa (y(x), c(.t)). W każdym kroku zbiór wierzchołków IV dzieli się na podzbiory ocechowanych i nie-ocechowanych. Wierzchołki ocechowane dzielą się na sprawdzone i nie* sprawdzone. W tej chwili s jest ocechowany i niesprawdzony.

3.    Pytamy: czy odpływ t jest ocechowany?

TAK: Koniec cechowania i skok do punktu 5.

NIE: Pytamy: czy istnieje wierzchołek ocechowany i niesprawdzony? TAK: skok do punktu 4.

NIE: Koniec procedury. Ostatnio otrzypiany przepływ jest mak* symalny, a zbiór W_x (ocechowanych do tej pory wierzchołków) tworzy przekrój minimalny (łP_t, IPj) ■ P^r,

4.    Wybieramy dowolny wierzchołek ,v, ocechowany i niesprawdzony, i sprawdzamy go:

a) Dla każdego y, który jest uieocechowanym następnikiem x, sprawdzamy, czy