Maksymalny przepływ -

algorytm Forda-Fulkersona

Ś

cie

ż

ka rozszerzaj

ą

ca

Jest to

ś

cie

ż

ka w sieci residualnej

(nieistniej

ą

ca w pierwotnej sieci !!!) ł

ą

cz

ą

c

ą

ź

ródło s z uj

ś

ciem t. Wszystkie kanały le

żą

ce

na

ś

cie

ż

ce rozszerzaj

ą

cej musz

ą

posiada

ć

niezerowe przepustowo

ś

ci residualne.

Przepustowo

ść

residualna

ś

cie

ż

ki

rozszerzaj

ą

cej jest równa najmniejszej

przepustowo

ś

ci residualnej kanałów

nale

żą

cych do tej

ś

cie

ż

ki:

c

f

(p) = min{c

f

(u,v) | (u,v)

∈

p}

Podstawowy algorytm Forda-

Fulkersona

Dopóki w sieci residualnej istnieje

ś

cie

ż

ka

rozszerzaj

ą

ca p, nale

ż

y zwi

ę

ksza

ć

przepływ o

c

f

(p) wzdłu

ż

kanałów zgodnych z kierunkiem

ś

cie

ż

ki, a zmniejsza

ć

przepływ wzdłu

ż

kanałów

przeciwnych (wygaszanie przepływu). Przepływ

sieciowy ro

ś

nie o c

f

(p).

Wyzerowa

ć

wszystkie przepływy w sieci

Przykład zastosowania

s

t

y

x

z

6

4

9

7

3

2

8

u

v

3

9

6

9

f(u,v) = 0 oraz | f

i

| = 0

Przepustowo

ść

residualna c

f

(u,v) = c(u,v) - f(u,v)

s

t

y

x

z

6

4

9

7

3

2

8

u

v

3

9

6

9

p = {s

→

u

→

v

→

t};

| f

i+1

| = | f

i

| + c

f

(p) = 0 + 6 = 6

c

f

(p) = 6

Poszukiwanie

ś

cie

ż

ki

rozszerzaj

ą

cej

6

6

u

v

Modyfikacja przepustowo

ś

ci

residualnych kraw

ę

dzi

ś

cie

ż

ki

rozszerzaj

ą

cej

s

t

y

x

z

4

9

3

2

8

u

v

3

9

6

| f

i+1

| = | f

i

| + c

f

(p) = 0 + 6 = 6

6

1

6

3

6

0

s

t

y

x

z

4

9

3

2

8

u

v

3

9

6

6

1

6

3

6

Poszukiwanie nowej

ś

cie

ż

ki rozszerzaj

ą

cej

p = {s

→

u

→

x

→

t}; c

f

(p) = 3

x

u

s

t

y

x

z

4

2

8

u

v

3

9

6

| f

i+2

| = | f

i+1

| + c

f

(p) = 6 + 3 = 9

6

1

6

3

6

3

9

Z poprzedniego kroku: | f

i+1

| = 6

Modyfikacja przepustowo

ś

ci residualnych

s

t

y

x

z

4

2

8

u

v

3

9

6

6

1

6

3

6

3

Poszukiwanie nowej

ś

cie

ż

ki rozszerzaj

ą

cej

p = {s

→

y

→

z

→

t};

6

9

c

f

(p) = 6

6

y

z

s

t

y

x

z

4

2

u

v

3

| f

i+3

| = | f

i+2

| + c

f

(p) = 9 + 6 = 15

6

1

6

3

6

3

Z poprzedniego kroku: | f

i+2

| = 9

6

2

9

6

6

3

Modyfikacja przepustowo

ś

ci residualnych

s

t

y

x

z

4

2

u

v

3

6

1

6

3

6

3

Nowa

ś

cie

ż

ka rozszerzaj

ą

ca

p = {s

→

y

→

x

→

t};

6

2

9

c

f

(p) = 3

6

6

3

y

x

s

t

y

x

z

4

2

u

v

| f

i+4

| = | f

i+3

| + c

f

(p) = 15 + 3 = 18

6

1

6

3

Z poprzedniego kroku: | f

i+3

| = 15

6

2

9

6

9

3

6

3

Modyfikacja przepustowo

ś

ci residualnych

s

t

y

x

z

4

u

v

s

t

y

x

z

6

4

9

7

3

2

8

u

v

3

9

6

9

6/6

0/4

6/9

6/7

3/3

0/2

6/8

3/3

9/9

6/6

9/9

Sie

ć

pierwotna