ขั้นตอนวิธีของดีนิซ
From Wikipedia, the free encyclopedia
ขั้นตอนวิธีของดีนิซ (อังกฤษ: Dinic's algorithm) เป็นขั้นตอนวิธีสำหรับการแก้ปัญหาการไหลมากสุด (อังกฤษ: Maximum flow) ในระบบเครือข่ายการไหล (อังกฤษ: Flow network) ถูกคิดขึ้นโดยเยฟิม ดีนิทซ์ (ฮีบรู: יפים (חיים) א 'דיניץ; อังกฤษ: Yefim (Chaim) A. Dinitz)[1] นักวิทยาศาสตร์คอมพิวเตอร์ชาวยิว (อดีตเป็นชาวรัสเซีย) ในปี ค.ศ. 1970 ขั้นตอนวิธีนี้จะใกล้เคียงกับขั้นตอนวิธีของเอ็ดมอนด์-คาป (อังกฤษ: Edmonds-Karp algorithm) ซึ่งใช้หลักการหาวิถีสั้นสุดและมีอัตราการเติบโตเป็นของเวลาทำงาน แต่ขั้นตอนวิธีของดีนิซจะมีอัตราการเติบโตที่น้อยกว่าคือ
ซึ่งเป็นผลมาจากการนำแนวคิดเรื่อง กราฟระดับ และ กระแสที่จำกัดการไหล มาใช้