7/23/2019 BAB 8 Ford Fulkerson

1/30

Algoritma Ford

7/23/2019 BAB 8 Ford Fulkerson

2/30

1950,

? Algoritma Ford-Fulkerson merupakan salah satu dari algoritma yang dipakaidalam aplikasi graph. Berdasarkan pengertiannya algoritma Ford-Fulkersonyaitu algoritma untuk memaksimumkan aliran (flow) dengan kapsitas danbiaya yang terbatas pada

jaringan.

? Algoritma Ford-Fulkerson juga merupakan metode yang dipakai untukmelakukan penambahan aliran dalam suatu jaringan.

2

kapasitasSebuahdigraphG=(V,E), yangmempunyaifungsikapasitaspadatiapsisi

(edge)disebutdenganjaringanberkapasitasPadajaringaniniterdapatduavertexygberbeda,

7/23/2019 BAB 8 Ford Fulkerson

3/30

6

5 15

38

t=6

7/23/2019 BAB 8 Ford Fulkerson

4/30

(i,j) .

? ConservationCondition? Untuk setiap vertex j , dimana j bukansumber s

atau tujuan t, maka penjumlahan aliran

yg masukke j sama dengan aliran yang ke luar dari j.

? feasibleflow.? Aliran yang memenuhi disebutconservation

condition feasible flow.

4

maximum flow

7/23/2019 BAB 8 Ford Fulkerson

5/30

5

flow

? flow? flow (aliran) dlm jaringan adalah nilaiinteger

fungsi f yg didefinisikan di tiap edge.

? 0 f(i,j) c(i,j) untuk setiap edge(i,j) .? ConservationCondition

? Untuk setiap vertex j , dimana j bukansumber s

atau tujuan t, maka penjumlahan aliran

7/23/2019 BAB 8 Ford Fulkerson

6/30

? tiga hal penting yang perlu diperhatikan dalam kaitannya dengan metodemenggunakan algoritma Ford-Fulkerson, yaitu:

? Residual network? Flow Augmenting Path

? Minimum Cutset

7

residual capacity

7/23/2019 BAB 8 Ford Fulkerson

7/30

rc flowflow rc

i j i j

Forward edge Backward edge

8

Residual network

? Residual network berisikan edges dengan flow yang lebih. Berikut diberikancontoh dari grafik residual network

7/23/2019 BAB 8 Ford Fulkerson

8/30

? Syarat dilakukan Flow Aughmenting Path? = ci,jfi,j0

? Langkah Flow Aughmenting Path:?

Menaikkanflow forwardlinksampaimenujuci,j? Menurunkan flowarahbackwardlinksampai

menuju 0 (kapasitas terendah)

10

7/23/2019 BAB 8 Ford Fulkerson

9/30

11

7/23/2019 BAB 8 Ford Fulkerson

10/30

12

Example: Augmenting

Path3/8 6/7 2/6 4/9

st

5 3 1 6 2 4 5 4

st

7/23/2019 BAB 8 Ford Fulkerson

11/30

excess flow capacity dari sebuahaugmentingpath sama dengan minimum dariresidual

capacities dari setiap edge dalampath.

4 4 0 7 1 5 4 5

st

7/23/2019 BAB 8 Ford Fulkerson

12/30

X W

4 55

s t

6 4

4

Z Y

4

0s

6

3 0

0 X W 55

0

0 t0

04 04

0

7/23/2019 BAB 8 Ford Fulkerson

13/30

3X W

2

5

1 3

3s 0 t

3

06

40

0 4ZY

16

Augmenting path

7/23/2019 BAB 8 Ford Fulkerson

14/30

4s 1 t

4

6

0

4

400

Z Y

17

Augmenting path

? Augmenting path: s->Z->Y->t? Excess capacity of s->Z->Y->t = min(6,4, 4) = 4

0

7/23/2019 BAB 8 Ford Fulkerson

15/30

18

Augmenting path

?At this point, there are no remainingaugmenting paths! Therefore the flow

is a maximum = 8.

4/43/3X

W

3/5

7/23/2019 BAB 8 Ford Fulkerson

16/30

Minimum cut-set

?Minimum cut-set yaitu suatu metodepemecahan jaringan menjadi beberapa subnet. Minimum cut-set akan

membentuk suatu partisi

(membentuk dua buah jaringanbaru)

7/23/2019 BAB 8 Ford Fulkerson

17/30

21

Al it F d F lk

7/23/2019 BAB 8 Ford Fulkerson

18/30

yg mempunyai f < c untuk seluruh arahfoward dan f> 0 untuk seluruh arah backward. JikaRoutine Amenemukan sebuah flow augmenting path,maka :

? Routine B? Routine B mengubah flow yg sesuai. Dengan kata lain, jika sudah tidak

terdapat augmenting path , maka flow sudah dipastikan optimal,sesuai dengan

teorema:

22

Theorem.

Sebuah flow f mempunyai nilai

7/23/2019 BAB 8 Ford Fulkerson

19/30

23

Tahapan-TahapanAlgoritmaFord- Fulkerson

? Terdapat dua tahapan dalam melakukan algoritmaFord-Fulkerson, yaitu:

1. Tahap pelabelan, terdiri atas beberapa tahap

a. simpul sumber dengan (0,)

b. Bila i merupakan simpul yang sudah dilabelkan dengan fi,j < ci,j ,

maka beri label untuk simpul j dengan (i, e(j)) di mana

e(j)=min(e(i), ci,j-fi,j).

Arah aliran dari i ke j

a. Bila i merupakan simpul yang sudah dilabelkan, jsimpul yang belum dilabelkan dan fj,i > 0, buat label

7/23/2019 BAB 8 Ford Fulkerson

20/30

b. untuk simpul-simpulyangterlabelkandengan

cara 1.c maka aliran dikurangifj,i=fi,j e(t)c. Setelahprosedurselesai,hapuslabel-labeltadi.

Kemudianulangiprosedurhinggatidak ditemukanlagi

aughmentingpath.

25

Tahapan-TahapanAlgoritmaFord- Fulkerson

?Jika kita mulai dengan setiap feasibleflow (e.g., f = 0). Secara umum, sebuah node dalam tiga kondisi

berikut:

7/23/2019 BAB 8 Ford Fulkerson

21/30

nned.

26

contohaliran

kapasitas

(6,3)24

7/23/2019 BAB 8 Ford Fulkerson

22/30

27

Prosedur pelabelan

1. Labelkan simpul satu dengan (+0,)

2. Pilih simpul yg SL (sudah label) tapi BS ( belumscan)?simpul 1dipilih

3. Simpul 1 sebagai simpul i. simpul i SL dan dan

labelkan setiapsimpul j yg BL (belum label)

? Cari fij < cij, kalau tidak ada cari fji > 0.? Jika fij < cij maka labelkan simpul j dengan (+i,(ej))dengan e(j)=min(e(i), ci,j - fi,j ).

? Jika fji>0, maka labelkan simpul j dgn (-i,e(j)) dimanae(j)=min(e(i),fji)

7/23/2019 BAB 8 Ford Fulkerson

23/30

Bila i merupakan simpul yang sudah dilabelkan danfi,j < ci,j , maka beri

label untuk simpul j dengan (i, e(j)) di mana e(j)= min (e(i), ci,j - fi,j ). Arah aliran dari i ke j

Labelkan simpul sumber dengan (+0,)

e(i)

(+1,3)

2

(6,3)

(+2,3)

4

(+0,)77

1

7/23/2019 BAB 8 Ford Fulkerson

24/30

Contoh penambahanaliranTujuan SL (sudah label)

Tambahkan fij+e=7+2=9(+1,3)

2

(6,3)

(+2,3)

4

(+0,)77

7/23/2019 BAB 8 Ford Fulkerson

25/30

Contoh penambahanaliran(6

,5)2

4

9 9

16

3

7/23/2019 BAB 8 Ford Fulkerson

26/30

Setelah prosedur selesai, hapus

label-label tadi. Kemudian ulangi prosedur hingga tidak ditemukan lagi

aughmenting path.

32

7/23/2019 BAB 8 Ford Fulkerson

27/30

99

16

3

(8,7)5

? Tidak bisa dilabelkan sampaitujuan,

artinya aliran jaringan sudahoptimal

33

7/23/2019 BAB 8 Ford Fulkerson

28/30

)2

4

(2,2)

9 9

16

3

(8,1)5

? Sumber di node 1 dan tujuan di

7/23/2019 BAB 8 Ford Fulkerson

29/30

35

7/23/2019 BAB 8 Ford Fulkerson

30/30

We start with the flow set equal to 0 everywhere:

36