Seminar Tugas Akhir

Agung Yudhianto
G05495026

Algoritma Dinic untuk Masalah Arus Maksimum

Transportasi barang dari lokasi sumber ke lokasi tujuan yang melewati beberapa lokasi-antara merupakan salah satu contoh masalah optimisasi yang dapat didefinisikan ke dalam bentuk graf (graph) atau lebih khusus lagi, jaringan (network). Jaringan transportasi (transportation network) merupakan bentuk khusus dari jaringan. Pada jaringan transportasi (transportation network) banyaknya barang/komoditas yang dapat ditransportasikan pada rute yang dilewati. Permasalahannya adalah menentukan arus maksimum yang dapat ditransportasikan sehingga memenuhi batasan-batasan tertentu, yang biasa dikenal dengan masalah arus maksimum (maximum flow problem). Masalah arus maksimum dapat juga dituliskan sebagai pemrograman linear, sehingga dapat diselesaikan dengan metode simpleks. Tetapi, telah banyak disusun metode/algoritma yang lebih efektif, antara lain Algoritma Dinic dan metode pelabelan Ford Fulkerson. Tulisan ini mempelajari Algoritma Dinic untuk menyelesaikan masalah arus maksimum. Algoritma Dinic memanfaatkan jaringan sisa (residual network) relatif terhadap suatu arus, yaitu jaringan dengan sisi-sisinya mempunyai kapasitas sisa positif. Pada jaringan sisa ini diidentifikasi f-augmenting path terpendek melalui layered network, kemudian dalam layered network dikontruksi suatu bloking flow yang dapat digunakan untuk menentukan arus maksimum.