Algoritma dinic untuk masalah arus maksimum

Abstract

Transportasi barang dari lokasi sumber ke lokasi tujuan yang me1ewati beberapa Iokasi-antara merupakan salah satu contoh masalah optimisasi yang dapat didefinisikan ke daIam bentuk graf (graph) atau lebih khusus !agi, jaringan (network). laringan transportasi (transporlalion network) merupakan bentuk khusus darijaringan. Padajaringan transportasi didefinisikan arus yang menyatakan banyaknya bai"ang I komoditas yang dapat ditransportasikan pada rote yang dilewati. Permasalahannya adalah m~tukan arus maksimum yang dapat ditransportasikan sehingga memenuhi batasan-batasan tertentu, yang biasa dikenal dengan masalah arus maksimum (maximumjIow problem), Masalah ams maksimurn dapat juga dituliskan sebagai pemrograman linear, sehingga dapat diselesaikan dengan metode simpleks. Tetapi, telah banyak diSUSWl metode I algoritma yang lebih efektif. antara lain Aigoritma OWe dan metode pelabelan Ford & Fulkerson