ขั้นตอนวิธีของดีนิซ

ขั้นตอนวิธีของดีนิซ  เป็นขั้นตอนวิธีสำหรับการแก้ปัญหาการไหลมากสุด  ในระบบเครือข่ายการไหล  ถูกคิดขึ้นโดยเยฟิม ดีนิทซ์  นักวิทยาศาสตร์คอมพิวเตอร์ชาวยิว (อดีตเป็นชาวรัสเซีย) ในปี ค.ศ. 1970 ขั้นตอนวิธีนี้จะใกล้เคียงกับขั้นตอนวิธีของเอ็ดมอนด์-คาป  ซึ่งใช้หลักการหาวิถีสั้นสุดและมีอัตราการเติบโตเป็นของเวลาทำงาน <math>O(VE^2)</math> แต่ขั้นตอนวิธีของดีนิซจะมีอัตราการเติบโตที่น้อยกว่าคือ <math>O(V^2E)</math> ซึ่งเป็นผลมาจากการนำแนวคิดเรื่อง "กราฟระดับ" และ "กระแสที่จำกัดการไหล" มาใช้
ประวัติ.
เยฟิม ดีนิทซ์ คิดค้นขั้นตอนวิธีนี้เพื่อตอบโจทย์แบบฝึกหัดก่อนชั้นเรียนในการเรียนขั้นตอนวิธีของอเดลสัน-เวลสกี ในขณะนั้นเขาไม่รู้ข้อเท็จจริงพื้นฐานเกี่ยวกับขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน
ดีนิทซ์กล่าวว่าการประดิษฐ์ขั้นตอนวิธีของเขาเกิดขึ้นในเดือนมกราคม พ.ศ. 2512 และได้รับการตีพิมพ์ในปี พ.ศ. 2513 ในวารสาร ("Doklady Akademii Nauk SSSR" ) ในปี พ.ศ. 2517 ชิมอน อีเวน (שמעון אבן) และ อลอน อีไต (אלון איתי , ซึ่งกำลังศึกษาปริญญาเอกในขณะนั้น) ที่สถาบันเทคโนโลยีอิสราเอลเทคนิออน (-) ในไฮฟา มีความสนใจและประทับใจกับขั้นตอนวิธีของดีนิทซ์ รวมถึงแนวคิดที่เกี่ยวข้องกับการปิดกั้นการไหลของอะเลคซันดร์ คาซานอฟ  อย่างไรก็ตาม มันยากสำหรับพวกเขาที่จะถอดรหัสเอกสารทั้งสองฉบับนี้ โดยแต่ละฉบับมีเพียงสี่หน้าเพื่อให้เป็นไปตามข้อจำกัดของวารสาร "Doklady Akademii Nauk SSSR" โดยไม่ท้อถอยหลังจากสามวันของความพยายามก็สามารถทำความเข้าใจเอกสารทั้งสองฉบับได้ ยกเว้นปัญหาการบำรุงรักษาเครือข่ายแบบชั้น ในอีกสองสามปีต่อมาอีเวน ได้บรรยายเกี่ยวกับ "ขั้นตอนวิธีของ Dinic" โดยออกเสียงชื่อผู้เขียนผิดในขณะที่เผยแพร่ให้เป็นที่รู้จัก อีเวนและอีไตมีส่วนร่วมในขั้นตอนวิธีนี้ด้วยการรวมการค้นหาในแนวกว้าง (BFS) และการค้นหาในแนวลึก (DFS) ซึ่งปัจจุบันเป็นวิธีที่นำเสนอขั้นตอนวิธีนี้โดยทั่วไป
เป็นเวลาประมาณ 10 ปีหลังจากที่ขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน ถูกประดิษฐ์ขึ้น ไม่มีใครรู้ว่ามันสามารถมีจุดสิ้นสุดในเวลาพหุนามในกรณีทั่วไปของความจุที่มีค่าขอบเป็นจำนวนอตรรกยะได้หรือไม่ สิ่งนี้ทำให้ไม่มีขั้นตอนวิธีเวลาพหุนามที่รู้จักสำหรับการแก้ปัญหาการไหลสูงสุดในกรณีทั่วไป ขั้นตอนวิธีของดีนิทซ์ และขั้นตอนวิธีของเอ็ดมอนด์-คาป (เผยแพร่ในปี พ.ศ. 2515) ทั้งสองแบบต่างแสดงให้เห็นว่าในขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน หากวิถีแต่งเติมแต่ละเส้นสั้นที่สุด ความยาวของวิถีแต่งเติมจะไม่มีการลดลงและขั้นตอนวิธีจะมีจุดสิ้นสุดเสมอ
นิยาม.
ให้ <math>G = ((V,E),c,s,t)</math> เป็นเน็ตเวิร์ก มีเส้นเชื่อมจาก <math>u</math> ไป <math>v</math> โดยอนุญาตให้กระแสไหลผ่านได้ <math>c(u,v)</math> และมีกระแสไหลผ่านแล้ว <math>f(u,v)</math>
 กราฟความจุคงเหลิอ (residual capacity) เป็นกราฟที่ได้จาก <math>c_f : V\times V \to R^+</math> นิยามโดย
# เมื่อ <math>(u,v)\in E</math>,
# : <math>c_f(u,v) = c(u,v) - f(u,v) </math>
# : <math>c_f(v,u) = f(u,v)</math>
# นอกเหนือจากนี้ <math>c_f(u,v) = 0</math>
 กราฟความจุคงเหลิอ คือกราฟ <math>G_f = ((V, E_f), c_f|_{E_f}, s, t)</math> ที่มี
 <math>E_f = \{(u,v)\in V \times V : c_f(u,v) > 0\}</math>
 วิถีแต่งเติม (augmenting path) คือวิถีจาก <math>s-t</math> ภายในกราฟความจุคงเหลิอ <math>G_f</math>
 ให้ <math>\operatorname{dist}(v)</math> แทนวิถีสั้นสุดจาก <math>s</math> ไป <math>v</math> ในกราฟ <math>G_f</math>
 จะได้ว่า "กราฟระดับ (level graph)" ของ <math>G_f</math> คือกราฟ <math>G_L = (V, E_L, c_f|_{E_L}, s,t)</math> ที่มี
 <math>E_L = \{(u,v)\in E_f : \operatorname{dist}(v) = \operatorname{dist}(u) + 1\}</math>
 กระแสจำกัดการไหล คือกระแสจาก <math>s</math> ไป <math>t</math> <math>f</math> ซึ่งทำให้ <math>G' = (V,E_L', s, t)</math> มี <math>E_L' = \{(u,v) : f(u,v) < c_f|_{E_L}(u,v)\}</math>และไม่มีวิถี <math>s-t</math> 
ขั้นตอนวิธี.
ขั้นตอนวิธีของดีนิซ
 "อินพุต" : เน็ตเวิร์ก <math>G = ((V, E), c, s, t)</math>
 "เอาต์พุต" : กระแส <math>s-t</math> ที่มีค่ากระแสสูงสุด <math>f</math>
วิเคราะห์.
จะเห็นได้ว่าจำนวนของเส้นเชื่อมในทุก กระแสจำกัดการไหล จะเพิ่มขึ้นอย่างน้อยที่ละ 1 ในการวน 1 รอบ และจะเพิ่มจนมีค่าไม่เกิน <math>V-1</math> โดย <math>V</math> เป็นจำนวนปมทั้งหมดในเน็ตเวิร์ก กราฟระดับ <math>G_L</math> สามารถสร้างได้จาก การค้นตามแนวกว้าง ในเวลา <math>O(E)</math> โดย <math>E</math> เป็นจำนวนเส้นเชื่อม และกระแสจำกัดการไหลในทุก ๆ กราฟระดับ จะสามารถหาได้ภายในเวลา <math>O(VE)</math> ดังนั้นขั้นตอนวิธีของดีนิซจึงใช้เวลาในการทำงานเป็น <math>O(V^2 E)</math> 
นอกจากนี้ยังสามารถทำให้ขั้นตอนวิธีของดีนิซมีประสิทธิภาพเพิ่มขึ้นด้วยการใช้โครงสร้างข้อมูลที่เรียกว่า ต้นไม้พลวัต (dynamic trees) ซึ่งจะทำให้เวลาการหากระแสจำกัดการไหลลดลงเป็น <math>O(E \log V)</math> ทำให้ขั้นตอนวิธีโดยรวมใช้ทำงานเพียง <math>O(VE \log V)</math>
กรณีพิเศษ.
ในเน็ตเวิร์กที่มีความจุเอกลักษณ์ จะมีขอบเขตของเวลามากขึ้น แต่ละขั้นตอนการปิดกั้นการไหลสามารถพบได้ในเวลา <math>O(E)</math> และสามารถแสดงให้เห็นว่าจำนวนเฟสไม่เกิน <math>O(\sqrt{E})</math> และ <math>O(V^{2/3})</math> ดังนั้นขั้นตอนวิธีจะทำงานในเวลา <math>O(\min\{V^{2/3}, E^{1/2}\}E)</math> 
ในเน็ตเวิร์กที่เกิดจากปัญหาบบการจับคู่สองส่วน]] จำนวนเฟสจะถูกจำกัดด้วย <math>O(\sqrt{V})</math> จึงนำไปสู่ขอบเขตเวลา <math>O(\sqrt{V} E)</math> ขั้นตอนวิธีที่ได้นั้นเรียกอีกอย่างว่าขั้นตอนวิธีฮอปครอฟต์-คาป โดยทั่วไป ขอบเขตนี้มีไว้สำหรับเน็ตเวิร์กเอกลักษณ์ใด ๆ — เครือข่ายที่จุดยอดแต่ละจุด ยกเว้นต้นทางและปลายทาง อาจมีวิถีของความจุขาเข้าเดียว หรือวิถีความจุของขาออกเดียว และความจุอื่นทั้งหมดเป็นจำนวนเต็มใด ๆ
ตัวอย่าง.
ให้ G เป็นเน็ตเวิร์กเริ่มต้น ซึ่งแต่ละเส้นเชื่อมจะมีขนาดของกระแสและความจุ <math>G_L</math> เป็นกราฟระดับ ปมที่มีเลขเป็นสีแดงคือค่าของ <math>\operatorname{dist}(v)</math> และวิถีสีน้ำเงินคือกระแสจำกัดการไหล