ANALISIS KINERJA ALGORITMA KARZANOV DALAM MENYELESAIKAN MAXIMUM FLOW PROBLEM

ANALISIS KINERJA ALGORITMA KARZANOV DALAM MENYELESAIKAN MAXIMUM FLOW PROBLEM Candrayani Methasari, Sapti Wahyuningsih, dan Susy Kuspambudi Andaini Universitas Negeri Malang ABSTRAK: Tujuan penulisan ini mendeskripsikan, menerapkan, menganalisis keunggulan dan kelemahan algoritma Karzanov pada maximum flow. Metode yang digunakan adalah membandingkan algoritma Karzanov dengan algoritma Dinitz dalam kasus. Kelebihan algoritma Karzanov yaitu (1) pembatasan layered network algoritma Dinitz,(2) running time sebesar O(n3),(3) efisien pada network dengan edge disjoint-st path dengan panjang berbeda, dan kelemahannya (4) kurang efisien pada network dengan edge disjoint st-path dengan panjang sama dimana kapasitas terkecil berada di tengah lintasan, dan (5) kurang efektif pada network dengan kapasitas irasional. Kata Kunci: Maximum flow, Algoritma Karzanov, Layered network ABSTRACT: The purpose of this paper is described, applied, and analyzed the advantages and disadvantages of Karzanov algorithm for maximum flow. A method that used of this study is compared the Karzanov algorithm with Dinitz algorithm into a number of case. The advantages of Karzanov algorithm that is (1) as a restriction the layered network in Dinitz algorithm, (2) takes O(n3) of running time, (3) more efficient to use in a network that has edge disjoint-st path with various lengths, and the disadvantages of this algorithm is (4) less efficient to use in a network which the entire edges are edge disjoint st-path with identical length; whereas the smallest capacity is located in the center of the edge, and (5) less effective in a network which has irrational capacity. Key Words: Maximum flow, Karzanov algorithm, Layered network

Dalam kehidupan sehari-hari Teori graph, khususnya maximum flow problem, dapat digunakan dalam pendistribusian produk dari pusat ke cabang dengan mengetahui jumlah kendaraan maksimal yang dikirimkan sekali periode pengiriman sehingga tidak menyebabkan kemacetan jalan, terutama di kota-kota besar. Penyelesaian maximum flow problem akan menjadi mudah dan efektif jika menggunakan algoritma. Setiap algoritma memiliki kelebihan dan kekurangan sehingga pemilihan algoritma yang tepat sangat diperlukan. Salah satu algoritma yang digunakan dalam menyelesaikan maximum flow problem adalah algoritma Dinitz. Pada Skripsi yang ditulis oleh Bahrul Ulum pada tahun 2010 dengan judul “Analisis Kinerja Algoritma Dinitz”, secara umum algoritma Dinitz menyelesaikan maximum flow problem dengan mengkonstruksi layered network dan blocking flow. Pembentukan layered network tidak memperhatikan seluruh titik. Pembentukan layered network ini akan membutuhkan waktu eksekusi lebih lama. Hal inilah yang mendasari adanya algoritma maximum flow lain untuk mengatasi permasalahan yang ada pada algoritma Dinitz. Salah satu algoritma tersebut adalah algoritma Karzanov. Pada Jurnal Internasional yang ditulis oleh Gary R.Waissi dengan judul “A New Karzanov-Type O(n3) Max-Flow Algorithm” pada tahun 1992 telah dipaparkan secara umum algoritma Karzanov. Algoritma ini dimulai dengan pembentukan layered network yang melibatkan semua titik dengan menggunakan

ide dasar pembentukan layered network algoritma Dinitz. Proses pencarian maximum flow pada algoritma Karzanov adalah menelusuri setiap titiknya dengan meningkatkan arus pada sisi melalui Forwardstep dan Backwardstep hingga semua titiknya menjadi seimbang. Penelusuran ini dilakukan secara bertahap dengan memperhatikan urutan layered network. Algoritma Karzanov dapat dikatakan bukan merupakan suatu algoritma yang baru. Sebenarnya algoritma ini telah diperkenalkan pada tahun 1974. Namun, algoritma Karzanov terkesan cenderung rumit untuk dipahami karena membutuhkan banyak algoritma lain dalam prosesnya maka jarang digunakan untuk menyelesaikan maximum flow problem. Kebanyakan orang memilih algoritma yang lebih sederhana untuk dipahami meskipun algoritma tersebut belum tentu menghasilkan nilai yang optimal. Berdasarkan latar belakang, penulisan ini mempunyai tujuan yaitu untuk (1) mendeskripsikan fase-fase yang digunakan dalam algoritma Karzanov untuk menyelesaikan maximum flow problem, (2) menerapkan algoritma Karzanov dalam menyelesaikan maximum flow problem, dan (3) menganalisis keunggulan dan kelemahan algoritma Karzanov dibandingkan dengan algoritma Dinitz. Menurut Hariyanto (2003), analisis algoritma digunakan untuk memprediksi kelakuan algoritma, sebagai sarana untuk pemilihan algoritma yang efisien, dan memperbaiki kinerja algoritma. Dalam menganalisis kinerja suatu algoritma dapat ditinjau dari sudut pandang efisiensi dan optimalitas algoritma tersebut. Efisiensi suatu algoritma didasarkan pada waktu tempuh atau “running time” yang dibutuhkan untuk menyelesaikan algoritma tersebut. Sedangkan suatu algoritma dikatakan optimal jika tidak ada algoritma lain di kelas persoalan itu yang punya jumlah operasi lebih sedikit dibanding algoritma itu sendiri. Kebaikan algoritma biasanya ditentukan oleh dua factor, yaitu: 1. Seberapa baik algoritma menyelesaikan masalah 2. Seberapa efisien algoritma menyelesaikan masalah Penilaian terhadap algoritma dilakukan dengan menggunakan analisis kuantitatif, yaitu analisis terhadap efisiensi algoritma dilakukan dengan melakukan perhitungan kompleksitas omputasi (waktu) dan ruang. Aspek kuantitatif mencoba mengukur seberapa besar source daya yang diperlukan suatu algoritma, baik seberapa cepat algoritma bekerja. Analisis ini dilakukan dengan membandingkan dua algoritma yaitu algoritma Karzanov dan algoritma Dinitz. Masing-masing permasalahan pada kedua algoritma dibentuk dalam kasus-kasus sehingga dapat diketahui keunggulan dan kelemahan kedua algoritma tersebut. HASIL YANG DIHARAPKAN Hasil yang diharapkan dari penulisan ini adalah 1. dapat menjelaskan dua fase pada algoritma Karzanov yaitu (1) mengkonstruksi acyclic layered network dan (2) mencari nilai maximum flow dengan menggunakan proses Forwardstep dan Backwardstep, 2. dapat menjelaskan contoh penerapan algoritma Karzanov melalui proses Forwardstep dan Backwardstep, 3. dapat menganalisis keunggulan dan kelebihan algoritma Karzanov dibandingkan dengan algoritma Dinitz.

PEMBAHASAN Pembahasan didasarkan pada hasil yang diharapkan mengenai deskripsi, penerapan, dan keunggulan serta kelemahan algoritma Karzanov. Berikut pembahasan dari masing-masing subbab. Algoritma Karzanov 1. Fase pertama adalah konstruksi acyclic layered network yang melibatkan semua titik. Misalkan , , 0, , , adalah acyclic layered network yang dikonstruksi dari network menggunakan algoritma Dinitz. Himpunan titik dinotasikan dengan . Himpunan arc dinotasikan dengan . Batas bawah arus pada arc adalah 0. Suatu vector kapasitas untuk arus pada arc adalah , dan adalah source serta adalah sink. Asumsikan bahwa dipartisi ke dalam himpunan tertentu , , … , dan , sedemikian sehingga untuk setiap , dengan , , untuk suatu dan 1. Himpunan titik , , … , , adalah layer pada dan adalah banyaknya layer, yang disebut panjang dari network . Setiap arc pada menghubungkan suatu titik pada layer tertentu ke titik pada layer yang lebih tinggi. 2. Fase kedua adalah fase untuk mencari nilai maksimum flow menggunakan 2 langkah yaitu Forwardstep dan Backwardstep. a. Forwardstep 1. Tambahkan arus pada semua arc , (yang keluar dari ) sesuai dengan kapasitas, kecuali pada arc , dimana diblok. 2. Misalkan layer terakhir yang diproses adalah ! . Proseslah layer dan usahakan untuk menyeimbangkan semua titik yang berikutnya tidak seimbang dan tidak diblok, dimana arus yang masuk lebih besar daripada arus yang keluar dari titik serta semua titik BackFlow yang diblok (BF-blocked). tidak diblok dan tidak seimbang dengan "#$%&', ( • Misalkan " ,')*&$ . Untuk menyeimbangkan yaitu dengan sepanjang arc , , menambahkan arus yang keluar dari dimana tidak diblok, satu arc berarah pada sebarang urutan. Jika usaha ini gagal dan arus yang keluar tidak dapat ditambahkan sepanjang arc , dan "#$%&', ( " ,')*&$ maka adalah titik Preflow yang diblok (PF-blocked). • Misalkan + adalah BF-blocked. Seimbangkan + dengan mengurangi arus yang pada arc , yang keluar dari + hingga + seimbang. Kurangi arus pada arc , , pertama di mana ' tidak diblok. 3. Ulangi langkah 2 untuk semua yang tidak seimbang tidak terblok dengan "#$%&', ( " ,')*&$ serta + tidak seimbang dan BF-blocked, dan semua layer dalam urutan naik pada layer bernomor hingga sink dicapai. 4. Jika tidak ada titik yang tidak seimbang, maka prune network. Jika proses ‘pruning’ mengeliminasi semua arc yang terkait dengan source atau sink , maka akhiri. Vektor arus feasible saat ini adalah maximal flow pada acyclic network. Sebaliknya, lanjutkan Backwardstep.

b. Backwardstep 1. Tambahkan arus pada semua arc , yang secara langsung masuk ke sink sesuai kapasitas, kecuali pada arc , dimana terblok. 2. Misalkan layer terakhir yang diproses adalah - . Lanjutkan dengan dan usahakan untuk menyeimbangkan semua titik yang tidak seimbang dan tidak terblok, dimana arus yang keluar ke titik lebih besar dari arus yang masuk ke titik tersebut, dan semua titik PFblocked. • Misalkan tidak terblok dan tidak seimbang dengan "#$%&', . " ,')*&$ . Usahakan untuk menyeimbangkan dengan menambah arus pada sepanjang arc /, dimana : 2 31 / 0 tidak terblok. Jika usaha tersebut gagal dan arus yang masuk ke tidak dapat ditingkatkan lagi pada sebarang arc /, dan "#$%&', . " ,')*&$ , maka buatlah titik BF-yang diblok (PFblocked). • Misalkan + adalah PF-blocked. Seimbangkan + dengan mengurangi arus pada arc 4, sampai + seimbang. Kurangi arus pada arc 4, terlebih dahulu untuk 5 tidak terblok. 3. Ulangi langkah 2 untuk semua yang tidak seimbang dan tidak terblok dengan "#$%&', . " ,')*&$ serta + yang tidak seimbang dan PF-blocked, dan semua layer dalam urutan turun pada layer bernomor samapi source dicapai. 4. Jika tidak ada titik yang tidak seimbang, maka prune network. Jika proses pruning mengeliminasi semua arc yang terkait dengan source atau sink , akhiri. Vektor feasible flow saat ini adalah maximal flow pada acyclic network. Sebaliknya, lanjutkan Forwardstep. Penerapan Algoritma Karzanov Berikut contoh penerapan algoritma Karzanov dalam suatu network N.

Gambar 1. Network N

(2) Backwardstep

(1) Forwardstep

(3) Forwardstep

Pada contoh network di Gambar 1, pencarian maximum flow menggunakan algoritma Karzanov membutuhkan dua proses Forwardstep dan satu proses Backwardstep. Pada proses Forwardstep pertama menghasilkan titik PF-blocked yaitu 6 sehingga keadaan titik tidak seimbang. Oleh karena itu, perlu dilakukan proses Backwardstep dengan harapan semua titik menjadi seimbang. Pada proses Backwardstep menghasilkan titik BF-blocked yaitu 7 sehingga perlu dilakukan proses Forwardstep kembali. Pada proses Forwardstep kedua ini menghasilkan semua titik dalam keadaan yang seimbang. Sehingga proses iterasi Forwardstep dan backwrdstep dihentikan. Kemudian dicari nilai maximum flow yang mengalir dari ke yaitu sebesar 8%9: 10. Keunggulan dan Kelemahan Algoritma Karzanov Keunggulan algoritma Karzanov yaitu (1) merupakan pembatasan layered network pada algoritma Dinitz sehingga pencarian lintasan membutuhkan waktu eksekusi sebesar ; 7 , (2) algoritma Karzanov mengalami paling banyak n-2 fase perulangan, Beberapa teorema pendukung mengenai keunggulan (1) dan (2) dari Jurnal Internasional oleh Gary R. Waissi (1992). Teorema 1. Kasus terburuk kompleksitas komputasi dari algoritma Karzanov adalah ; < . Bukti: Pada kasus khusus ketika arus meningkat dari ke kemungkinan yang terjadi bahwa tidak ada titik yang terblok. Jika hal ini terjadi maka semua titik seimbang setelah Forwardstep dan semua arc yang keluar dari sesuai dengan kapasitasnya, yaitu arus menjadi maksimal hanya setelah dilakukan Forwardstep. Diluar kasus khusus tersebut, berikut ini perlu diperhatikan. Pada permulaan masing-masing Forwardstep hanya titik yang tidak seimbang yang mana menjadi tidak seimbang dari Backwardstep sebelumnya. Titik tersebut disebut BF-blocked yang tidak seimbang. Secara sama, pada permulaan masingmasing Backwardstep hanya titik yang tidak seimbang yang mana menjadi tidak seimbang dari Forwardstep sebelumnya. Titik tersebut disebut PF-blocked yang tidak seimbang. Setiap barisan Forwardstep dan Backwardstep keduanya paling sedikit memblok dan menyeimbangkan satu titik. Selama Forwardstep paling sedikit satu titik merupakan titik PF-blocked atau BF-blocked menjadi seimbang. Selama Forwardstep paling sedikit satu titik merupakan titik PF-blocked atau BF-blocked menjadi seimbang. Selama Backwardstep paling sedikit satu titik merupakan titik BF-blocked atau PF-blocked menjadi seimbang. Titik PF-blocked yang tidak seimbang hanya adapat menjadi titik PF-blocked yang seimbang. Secara sama, titik BF-blocked yang tidak seimbang hanya dapat menjadi titik BFblocked yang seimbang. Jika pada titik PF or BF- blocked menjadi seimbang, maka arc yang terkait dengan titik tersebut tidak digunakan untuk meningkatkan arus pada subsekuen langkah dari algoritma tersebut. Ada paling banyak 32 !< < perulangan pada Forwardstep dan Backwardstep dan paling banyak ∑ ? usaha untuk penyeimbangan. Arus pada arc , ditambah pada Forwardstep jika dan hanya jika tidak terblok. Arus pada arc , ditambah pada Backwardstep jika dan hanya jika tidak terblok. Secara sama, arus pada arc , dikurangi pada Forwardstep jika

dan hanya jika adalah BF-blocked. Arus pada arc , dikurangi pada Backwardstep jika dan hanya jika adalah PF-blocked. Jadi, arus pada suatu arc pertamanya ditambah kemudian dikurangi. Penambahan arus terus dilakukan ketika arc telah jenuh atau berhenti ketika titik berturut-turut telah seimbang. Pengurangan arus lainnya mengurangi arus pada arc menjadi 0 atau berhenti ketika titik berturut-turut telah seimbang. Pada masing-masing sekuen Forwardstep dan Backwardstep, satu titik diblok atau titik yang terblok diseimbangkan. Perhatikan pada sekuen ke dari langkah tersebut pada acyclic network. Misalkan selama sekuen ini titik yang terblok menjadi seimbang. Misalkan juga ada @ arc yang terkait dengan titik tersebut. Setiap kali titik yang terblok diseimbangkan, maka titik itu sendiri dan arc yang terkait dengan titik tersebut tidak diperhatikan karena pemambahan arus pada langkah subsekuen dari algoritma tersebut. Jadi, secara jelas bahwa ∑ @ : A 4 ""C 2 D. Jadi total usaha yang dibutuhkan oleh algoritma < tersebut adalah paling banyak ; D ; < . Corollary. Algoritma Karzanov membutuhkan paling banyak usaha O(n3) untuk suatu nilai maximum flow pada nonacyclic directed network G. Bukti: Maximum flow pada acyclic network membutuhkan paling banyak usaha O(n2). Algoritma Dinitz mengurangi nilai maximum flow problem untuk menyelesaikan paling banyak n-1 maximal flow problem pada acyclic network. Oleh karena itu, nilai maximum flow pada network asal G dapat dicari pada paling banyak (n-1)n2 langkah., yaitu usaha O(n3). Keunggulan lain dari algoritma Karzanov yaitu (3) efisien dalam menyelesaikan masalah network yang seluruh lintasannya merupakan edge disjoint-st path dengan panjang yang berbeda. Keunggulan (3) dapat dijelaskan dalam kasus dengan network seperti pada Gambar 2 berikut.

Gambar 2. Network N

Gambar 3. Residual Network N

8 8 8 < Diperoleh nilai maksimum flow sebesar ∑ 8 8 E 8 F 5 2 1 2 1 11 Jika penyelesaian menggunakan algoritma Dinitz maka kita akan mengkonstruksi layered network sebanyak lintasan yang ada dan akan melakukan blocking flow sebanyak lintasan yang ada pula. Jika terdapat 20 edge disjoint-st path maka kita akan mengkonstruksi layered network sebanyak 20 lintasan dan melakukan blocking flow sebanyak 20 lintasan pula. Tetapi dengan menggunakan algorita Karzanov, hanya mengkonstruksi 1 layered network dan

langsung melakukan proses Forwardstep dan Backwardstep sehingga ditemukan nilai maksimum flow. Apabila dalam kasus yang sama, namun hanya berbeda kapasitas pada arc dimana kapasitas , HI kapasitas , dan kapasitas tersebut lebih kecil dari kapasitas arc yang lain yang tidak terikat dengan dan , maka hanya perlu waktu eksekusi untuk konstruksi layered network sekali dan proses Forwardstep sekali sehingga langsung ditemukan nilai maksimum flow. Di balik keunggulan tersebut, terdapat beberapa kelemahan yang terdapat pada algoritma Karzanov yaitu sebagai berikut. (1) kurang efisien jika digunakan pada network yang seluruh lintasannya merupakan edge disjoint st-path dengan panjang yang sama dimana kapasitas terkecil berada di tengah lintasan

Gambar 4. Network N

Gambar 5. Residual Network N

Nilai maximum flow yang diperoleh sebesar 3. Nilai ini adalah nilai maximal karena sama dengan nilai min cut yaitu 3. Tetapi, untuk kasus seperti ini, algoritma Karzanov memerlukan iterasi yang panjang untuk memprosesnya melalui Forwardstep dan Backwardstep karena langkah pertama untuk masingmasing step adalah menambahkan arus sesuai kapasitas. Hal ini menyebabkan Forwardstep maupun Backwarstep akan diproses berulang kali. Dalam contoh ini, proses Forwardstep dilakukukan sebanyak tiga kali sedangkan proses Backwardstep dilakukan sebanyak dua kali. Misalkan terdapat network seperti gambar 4 dengan panjang lintasan dari ke adalah 51. Diketahui sisi I adalah sisi yang memuat kapasitas terkecil yang berada di antara titik dan , dimana panjang lintasan dari ke I sebesar 25 dan panjang lintasan dari ke sebesar 25, maka penyelesaian menggunakan algoritma Karzanov akan membutuhkan iterasi yang panjang dengan memerlukan proses Forwardstep sebanyak 25 kali dan proses Backwardstep sebanyak 25 kali pula. Tentu hal ini tidak efektif jika dibandingkan dengan algoritma Dinitz yang hanya memerlukan iterasi masing-masing satu kali untuk konstruksi layered network dan blocking flow. Oleh karena itu, penerapan algoritma Karzanov pada network yang memiliki edge disjoint-st path dengan panjang yang sama dan kapasitas sisi di tengah-tengah lintasan sangat kecil dapat dikatakan kurang efisien karena membutuhkan running time proses Forwardstep dan Backwardstep lebih lama dibandingkan algoritma Dinitz. (2) kurang efektif jika digunakan pada network yang memiliki sisi berkapasitas irrasional Misalkan

7!√< K

L 0,317.

Gambar 6. Network N

Gambar 7. Residual Network N

Berdasarkan residual network pada Gambar 7 diperoleh nilai maximum flow sebesar 8 8 < 8 7 2 2 23 23 6. Jika menggunakan algoritma Dinitz diperoleh nilai maximum flow sebesar 9. Hal ini dikarenakan pemilihan blocking flow pada layered network secara kebetulan tidak melintasi kapasitas yang memuat nilai sehingga hasil yang diperoleh lebih maksimum. Sedangkan jika menggunakan algoritma Karzanov, dimana untuk mencari nilai maximum flow dengan menelusuri setiap titik dan arc yang terkait dari layer ke layer berikutnya, maka ada kemungkinan akan melintasi arc yang memuat kapasitas bernilai , sehingga nilai maximum flow yang diperoleh tidak maksimum. Oleh karena itu, penerapan algoritma Karzanov pada network yang memiliki kapasitas irrasional dikatakan kurang efektif karena nilai flow yang dihasilkan tidak selalu maksimum. (3) memerlukan banyak algoritma lain untuk mengkonstruksi acyclic layered network sehingga terkesan lebih rumit untuk dipahami SIMPULAN DAN SARAN Kesimpulan Setelah dilakukan analisis dan pembahasan maka diperoleh simpulan mengenai (1) pendeskripsian fase-fase algoritma Karzanov, (2) penerapan algoritma Karzanov, dan (3) keunggulan serta kelemahan algoritma Karzanov. Pertama, Algoritma Karzanov merupakan salah satu algoritma yang digunakan untuk mencari maximum flow dan nilai maximum flow pada suatu network. Pada algoritma Karzanov, untuk mencari arus maksimum menggunakan dua fase. Fase pertama, acyclic layered network yang dikonstruksi dengan menggunakan algoritma Dinitz yang melibatkan semua titiknya. Jadi, layered network yang dikonstruksi pada algoritma Karzanov merupakan pembatasan layered network pada algoritma Dinitz. Fase kedua, algoritma ini bertujuan menerapkan acyclic layered network untuk mencari nilai arus maksimum pada network asal. Algoritma Karzanov dalam proses pencarian nilai maximum flow menggunakan Forwardstep dan Backwardstep. Forwardstep adalah langkah dimana semua titik diseimbangkan dari layer pertama hingga layer terakhir. Sedangkan Backwardstep adalah langkah dimana semua titik diseimbangkan dari layer terakhir hingga layer pertama. Proses ini dilakukan berulang secara bergantian dan berhenti ketika semua titik telah seimbang. Kemudian, yang kedua, secara umum dalam penerapannya algoritma Karzanov lebih cepat dalam mencari nilai maximum flow. Algoritma Karzanov tidak memerlukan konstruksi layered network secara berulang sehingga tidak membutuhkan waktu penyelesaian yang terlalu lama.

Ketiga, dengan menggunakan pembatasan layered network pada algoritma Dinitz, pencarian lintasan dari source ke sink membutuhkan waktu eksekusi atau running time sebesar ; 7 . Nilai running time ini secara umum lebih baik daripada nilai running time pada Algoritma Dinitz yaitu ; < D . Algoritma Karzanov mengalami paling banyak n-2 fase perulangan. Keunggulan lain algoritma ini dibandingkan algoritma Dinitz adalah efisien dalam menyelesaikan masalah network yang seluruh lintasannya merupakan edge disjoint-st path dengan panjang yang berbeda. Namun, algoritma Karzanov memiliki kekurangan yaitu kurang efisien jika digunakan pada network yang seluruh lintasannya merupakan edge disjoint st-path dengan panjang yang sama dimana kapasitas terkecil berada di tengah lintasan, kurang efektif jika digunakan pada network yang memiliki sisi berkapasitas irrasional, dan memerlukan banyak algoritma lain dalam pengkonstruksian acyclic layered network sehingga terkesan lebih rumit untuk dipahami. Saran Penulis menyarankan permasalahan maximum flow problem dengan kasus dimana network asal memiliki edge disjoint-st path dengan panjang berbeda akan lebih efisien jika diselesaikan dengan algoritma Karzanov. Berdasarkan langkahlangkah algoritma Karzanov dan contoh penerapan algoritma Karzanov sebaiknya dapat ditindak lanjuti dengan membuat program penyelesaian maximum flow problem menggunakan algoritma Karzanov sehingga lebih mudah untuk diaplikasikan. Selain pembahasan pada algoritma Karzanov dengan menggunakan proses Forwardstep dan Backwardstep, pembaca dapat merujuk algoritma Karzanov dengan tipe lain yang menggunakan tiga tahap, yaitu (1) konstruksi residual R 8 , (2) advance the preflow pada Q R 8 , dan (3) balance the subnetwork Q R 8 . preflow pada Q DAFTAR RUJUKAN Hariyanto, Bambang. 2003. Struktur Data Memuat Dasar Pengembangan Orientasi Objek. Bandung: Informatika. Ulum, Bahrul. 2010. Analisis Kinerja Algoritma Dinitz. Skripsi tidak diterbitkan. Malang: FMIPA Universitas Negeri Malang. Waissy, Gary. R. 1992. A New Karzanov-type ; 7 Max-Flow Algorithm (online),(http://deepblue.lib.umich.edu/bitstream/2027.42/30217/1/0000 609.pdf , diakses 23 Maret 2012).

Artikel oleh Candrayani Methasari ini Telah diperiksa pada tanggal 8 Januari 2013

Pembimbing I

Dra. Sapti Wahyuningsih, M.Si. NIP 19621211 198812 2 001 Pembimbing II

Dra. Susy Kuspambudi Andaini, M.Kom. NIP 19590419 198812 2 001

Mahasiswa

Candrayani methasari NIM 309312422756