Petunjuk dan konteks
Setiap edge berarah memiliki kapasitas dan biaya unit. Kirimkan aliran hingga batas tertentu dari s ke t, dengan meminimalkan biaya di antara solusi yang memiliki aliran yang sama. Kembalikan aliran aktual dan biayanya sambil menangani edge residual balik, biaya negatif, edge paralel, simpul pembuangan yang tidak dapat dijangkau, dan integer overflow.
Apa yang sedang diuji oleh pewawancara
- Apakah Anda membangun edge residual dan biaya balik dengan benar.
- Apakah Anda dapat menggunakan successive shortest paths atau potensial dengan edge negatif.
- Apakah Anda memisahkan tujuan aliran maksimum dari penentu kelayakan biaya minimum.
- Apakah Anda menyatakan kompleksitas, batasan overflow, dan pengujian berbasis properti (property-based tests).
Pertanyaan klarifikasi sebelum menjawab
Konfirmasikan kapasitas dan biaya bernilai bulat, siklus berbiaya negatif yang diizinkan, persyaratan batas eksak, ukuran graf, dan batasan biaya. Jika siklus negatif diizinkan, perjelas apakah pengurangan biaya tanpa batas merupakan bagian dari model dan bagaimana potensial awal diperoleh.
Kerangka jawaban 30 detik
Untuk setiap edge input, tambahkan edge residual maju dan edge balik berkapasitas nol dengan biaya yang dinegasikan. Temukan jalur terpendek dari s ke t secara berulang dalam graf residual dan augmentasikan nilai batas terkecilnya (bottleneck) hingga batas terpenuhi atau tidak ada jalur yang tersisa. Jika biaya bisa bernilai negatif, hitung potensial awal dengan Bellman-Ford, lalu beri bobot ulang pada edge sehingga Dijkstra valid digunakan. Kompleksitas bergantung pada augmentasi dan implementasi jalur terpendek, tidak hanya pada kompleksitas aliran maksimum biasa.
Pembahasan mendalam langkah demi langkah
1. Struktur edge residual
Simpan tujuan, indeks balik, kapasitas residual, dan biaya. Augmentasi mengurangi kapasitas maju, meningkatkan kapasitas balik, dan menambahkan aliran dikali biaya ke total keseluruhan. Edge balik memungkinkan jalur berikutnya membatalkan pilihan sebelumnya, yang sangat penting untuk mencapai biaya optimal.
2. Jalur terpendek dan potensial
Dengan biaya non-negatif, Dijkstra sudah cukup. Dengan biaya negatif tetapi tanpa siklus negatif, pertahankan potensial per simpul, hitung jalur terpendek menggunakan biaya tereduksi (reduced costs), lalu perbarui nilai potensial. Jangan pernah menerapkan Dijkstra biasa secara langsung pada graf yang berisi edge negatif.
3. Augmentasi dan penghentian
Jumlah augmentasi adalah nilai minimum dari sisa batas, bottleneck jalur, dan batas batch apa pun. Berhenti ketika tidak ada jalur yang ada dan kembalikan aliran aktual; jika batas eksak diperlukan, laporkan ketidaklayakan (infeasibility). Gunakan tipe integer yang lebar dan periksa perkalian sebelum mengakumulasikan biaya.
Contoh jawaban berkualitas tinggi
Saya akan menyimpan edge residual dalam daftar ketetanggaan (adjacency lists) dan menambahkan setiap pasangan maju dan balik secara bersamaan. Loop utama mencari jalur terpendek dari s ke t di antara edge berkapasitas positif, mengaugmentasikannya, dan memperbarui biaya. Dijkstra berfungsi untuk biaya non-negatif; dengan biaya negatif dan tanpa siklus negatif, hitung potensial awal dan pertahankan biaya tereduksi tetap non-negatif. Batasi setiap augmentasi dengan sisa permintaan dan bottleneck jalur. Jika pembuangan menjadi tidak dapat dijangkau, kembalikan aliran aktual dan tandai target yang tidak terpenuhi sebagai tidak layak. Pengujian mencakup pembatalan balik, edge paralel, kapasitas nol, biaya negatif, graf terputus, aliran parsial, asumsi siklus negatif, dan overflow biaya besar. Model ini cocok dengan formulasi aliran biaya minimum OR-Tools, tetapi kompleksitas harus menyebutkan faktor simpul, edge, dan augmentasi; ini tidak secara otomatis bernilai polinomial dalam kapasitas numerik.
Kesalahan umum
- Melupakan edge balik atau memberikannya biaya positif dan bukan biaya yang dinegasikan.
- Menjalankan Dijkstra secara langsung ketika edge residual dapat memiliki biaya negatif.
- Mengaugmentasikan hanya satu unit per jalur terpendek tanpa justifikasi.
- Memperlakukan aliran maksimum dan biaya minimum sebagai satu kunci pengurutan yang tidak dibedakan.
- Mengakumulasikan nilai kapasitas-dikali-biaya yang besar dalam tipe integer yang sempit.
Pertanyaan lanjutan dan tanggapan
Mengapa edge balik dapat memperbaiki pilihan sebelumnya?
Edge balik merepresentasikan penarikan kembali aliran yang dikirim sebelumnya dan meniadakan biaya aliran tersebut. Jalur terpendek berikutnya dapat menggunakannya untuk menata ulang solusi dan menurunkan total biaya.
Kapan Anda membutuhkan Bellman-Ford?
Ketika graf residual awal memiliki edge berbiaya negatif tetapi tidak memiliki siklus negatif, gunakan algoritma tersebut atau metode yang setara untuk menghitung potensial awal; setelah itu biaya tereduksi non-negatif memungkinkan penggunaan Dijkstra.
Bagaimana jika aliran yang diminta tidak dapat dicapai?
Hentikan dan kembalikan aliran aktual serta biaya dengan hasil tidak layak (infeasible) yang eksplisit. Jika bisnis memerlukan target tersebut tercapai, pemanggil harus melakukan rollback atau memilih jaringan cadangan daripada memperlakukan aliran parsial sebagai keberhasilan.