อัลกอริทึม Push-Relabel
อัลกอริทึม Push-Relabel ซึ่งพัฒนาโดย Andrew V. Goldberg และ Robert E. Tarjan ในปี 1988 เป็นวิธีการที่มีประสิทธิภาพสูงในการคำนวณการไหลสูงสุดในเครือข่าย แตกต่างจากวิธีการแบบเส้นทางเสริม (augmenting path methods) อัลกอริทึมนี้จะรักษา preflow และใช้การดำเนินการ push และ relabel ในระดับท้องถิ่นและระดับโลกเพื่อขับเคลื่อนการไหลไปยัง sink ทำให้ได้ความซับซ้อนในกรณีที่แย่ที่สุด (worst-case complexity) ที่เหนือกว่า
อ่านวิธีฉบับเต็ม
เข้าสู่ระบบด้วยบัญชีฟรีเพื่ออ่านส่วนนี้
Method map
The neighbourhood of related methods — select a node to explore.
แหล่งอ้างอิง
- Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940. DOI: 10.1145/48014.61051 ↗
- Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin. link ↗
วิธีอ้างอิงหน้านี้
ScholarGate. (2026, June 3). Push-Relabel Algorithm for Maximum Flow. ScholarGate. https://scholargate.app/th/operations-research/push-relabel-algorithm
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- ขั้นตอนวิธีเบลล์แมน-ฟอร์ดการวิจัยดำเนินงาน↔ compare
- ขั้นตอนวิธีของ Dijkstraการวิจัยดำเนินงาน↔ compare
- อัลกอริทึม Ford-Fulkersonการวิจัยดำเนินงาน↔ compare