384 385

384 Programowanie sieciowe

Tablica 8.1

Krawędź	Przepustowości poprzednie		Przepustowości nowe
1-2	5	0	5-2 = 3	0 + 2 = 2
2-3	2	2	2-2 = 0	2 + 2 = 4
3-5	4	0	4-2=2	0 + 2 = 2
5-7	3	0	3-2=1	0 + 2 = 2

Iteracja 2

Konstruujemy drugą drogę od źródła do ujścia. Wykorzystujemy w tym celu sieć przepływu ze zmodyfikowanymi przepustowościami, przedstawioną na rys. 8.20. Proponowana obecnie droga przechodzi przez wierzchołki 1-2-5-7. Porównanie wyróżnionych wartości przepływu wskazuje na to, że przepustowość tej drogi jest równa 1 (rys. 8.21).

Rysunek 8.21

Obliczamy nowe przepustowości dla krawędzi, które zostały wykorzystane w skonstruowanym przepływie. Wyniki obliczeń ilustruje tablica 8.2.

Tablica 8.2

Krawędź	Przepustowości poprzednie		Przepustowości nowe
1-2	3	2	3-1=2	2 + 1=3
2-5	1	2	1-1=0	2+1=3
5-7	1	2	1-1=0	2+1=3

Iteracja 3

Konstruujemy trzecią drogę od źródła do ujścia. Wykorzystujemy sieć przepływu ze zmodyfikowanymi w poprzednich iteracjach przepustowościami. Otrzymujemy drogę 1-2-6-7. Porównanie wyróżnionych wartości przepływu wskazuje na to, że przepustowość tej drogi jest równa 2 (rys. 8.22).

Rysunek 8.22

t ł-pi»OC ; _v

Iteracja 3

Obliczamy nowe przepustowości dla krawędzi, które zostały wykorzystane w rozpatrywanym przepływie. Sposób obliczania nowych przepustowości ilustruje tablica 8.3.