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

**ขั้นตอนวิธีของดีนิซ** () เป็นขั้นตอนวิธีสำหรับการแก้ปัญหาการไหลมากสุด () ในระบบเครือข่ายการไหล () ถูกคิดขึ้นโดยเยฟิม ดีนิทซ์ (; ) นักวิทยาศาสตร์คอมพิวเตอร์ชาวยิว (อดีตเป็นชาวรัสเซีย) ในปี ค.ศ. 1970 ขั้นตอนวิธีนี้จะใกล้เคียงกับขั้นตอนวิธีของเอ็ดมอนด์-คาป () ซึ่งใช้หลักการหาวิถีสั้นสุดและมีอัตราการเติบโตเป็นของเวลาทำงาน O(VE^2) แต่ขั้นตอนวิธีของดีนิซจะมีอัตราการเติบโตที่น้อยกว่าคือ O(V^2E) ซึ่งเป็นผลมาจากการนำแนวคิดเรื่อง *กราฟระดับ* และ *กระแสที่จำกัดการไหล* มาใช้

## ประวัติ
เยฟิม ดีนิทซ์ คิดค้นขั้นตอนวิธีนี้เพื่อตอบโจทย์แบบฝึกหัดก่อนชั้นเรียนในการเรียนขั้นตอนวิธีของอเดลสัน-เวลสกี ในขณะนั้นเขาไม่รู้ข้อเท็จจริงพื้นฐานเกี่ยวกับขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน

ดีนิทซ์กล่าวว่าการประดิษฐ์ขั้นตอนวิธีของเขาเกิดขึ้นในเดือนมกราคม พ.ศ. 2512 และได้รับการตีพิมพ์ในปี พ.ศ. 2513 ในวารสาร  (*Doklady Akademii Nauk SSSR*&thinsp;) ในปี พ.ศ. 2517 ชิมอน อีเวน (שמעון אבן) และ อลอน อีไต (אלון איתי , ซึ่งกำลังศึกษาปริญญาเอกในขณะนั้น) ที่สถาบันเทคโนโลยีอิสราเอลเทคนิออน ( - ) ในไฮฟา มีความสนใจและประทับใจกับขั้นตอนวิธีของดีนิทซ์ รวมถึงแนวคิดที่เกี่ยวข้องกับการปิดกั้นการไหลของอะเลคซันดร์ คาซานอฟ () อย่างไรก็ตาม มันยากสำหรับพวกเขาที่จะถอดรหัสเอกสารทั้งสองฉบับนี้ โดยแต่ละฉบับมีเพียงสี่หน้าเพื่อให้เป็นไปตามข้อจำกัดของวารสาร *Doklady Akademii Nauk SSSR* โดยไม่ท้อถอยหลังจากสามวันของความพยายามก็สามารถทำความเข้าใจเอกสารทั้งสองฉบับได้ ยกเว้นปัญหาการบำรุงรักษาเครือข่ายแบบชั้น ในอีกสองสามปีต่อมาอีเวน ได้บรรยายเกี่ยวกับ "ขั้นตอนวิธีของ Dinic" โดยออกเสียงชื่อผู้เขียนผิดในขณะที่เผยแพร่ให้เป็นที่รู้จัก อีเวนและอีไตมีส่วนร่วมในขั้นตอนวิธีนี้ด้วยการรวมการค้นหาในแนวกว้าง (BFS) และการค้นหาในแนวลึก (DFS) ซึ่งปัจจุบันเป็นวิธีที่นำเสนอขั้นตอนวิธีนี้โดยทั่วไป

เป็นเวลาประมาณ 10 ปีหลังจากที่ขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน ถูกประดิษฐ์ขึ้น ไม่มีใครรู้ว่ามันสามารถมีจุดสิ้นสุดในเวลาพหุนามในกรณีทั่วไปของความจุที่มีค่าขอบเป็นจำนวนอตรรกยะได้หรือไม่ สิ่งนี้ทำให้ไม่มีขั้นตอนวิธีเวลาพหุนามที่รู้จักสำหรับการแก้ปัญหาการไหลสูงสุดในกรณีทั่วไป ขั้นตอนวิธีของดีนิทซ์ และขั้นตอนวิธีของเอ็ดมอนด์-คาป (เผยแพร่ในปี พ.ศ. 2515) ทั้งสองแบบต่างแสดงให้เห็นว่าในขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน หากวิถีแต่งเติมแต่ละเส้นสั้นที่สุด ความยาวของวิถีแต่งเติมจะไม่มีการลดลงและขั้นตอนวิธีจะมีจุดสิ้นสุดเสมอ

## นิยาม
ให้ G = ((V,E),c,s,t) เป็นเน็ตเวิร์ก มีเส้นเชื่อมจาก u ไป v โดยอนุญาตให้กระแสไหลผ่านได้ c(u,v) และมีกระแสไหลผ่านแล้ว f(u,v)

: **กราฟความจุคงเหลิอ (residual capacity)** เป็นกราฟที่ได้จาก c_f : V\times V \to R^+ นิยามโดย
:# เมื่อ (u,v)\in E,
:# : c_f(u,v) = c(u,v) - f(u,v) 
:# : c_f(v,u) = f(u,v)
:# นอกเหนือจากนี้ c_f(u,v) = 0

: **กราฟความจุคงเหลิอ** คือกราฟ G_f = ((V, E_f), c_f|_{E_f}, s, t) ที่มี
:: E_f = \{(u,v)\in V \times V : c_f(u,v) > 0\}

: **วิถีแต่งเติม (augmenting path)** คือวิถีจาก s-t ภายในกราฟความจุคงเหลิอ G_f

: ให้ \operatorname{dist}(v) แทนวิถีสั้นสุดจาก s ไป v ในกราฟ G_f
: จะได้ว่า *กราฟระดับ (level graph)* ของ G_f คือกราฟ G_L = (V, E_L, c_f|_{E_L}, s,t) ที่มี
:: E_L = \{(u,v)\in E_f : \operatorname{dist}(v) = \operatorname{dist}(u) + 1\}

: **กระแสจำกัดการไหล** คือกระแสจาก s ไป t f ซึ่งทำให้ G' = (V,E_L', s, t) มี E_L' = \{(u,v) : f(u,v) และไม่มีวิถี s-t 

## ขั้นตอนวิธี
**ขั้นตอนวิธีของดีนิซ**
: *อินพุต*&thinsp;: เน็ตเวิร์ก G = ((V, E), c, s, t)
: *เอาต์พุต*&thinsp;: กระแส s-t ที่มีค่ากระแสสูงสุด f
# กำหนดf(e) = 0 สำหรับทุก e\in E
# สร้าง G_L จาก G_f ของ G ถ้า \operatorname{dist}(t) = \infty ให้หยุดและคืนค่า f
# หากระแสจำกัดการไหล f\;' ใน G_L
# ขยายกระแส\ f ด้วย f\;' จากนั้นกลับไปทำขั้นตอนที่ 2

## วิเคราะห์
จะเห็นได้ว่าจำนวนของเส้นเชื่อมในทุก กระแสจำกัดการไหล จะเพิ่มขึ้นอย่างน้อยที่ละ 1 ในการวน 1 รอบ และจะเพิ่มจนมีค่าไม่เกิน V-1 โดย V เป็นจำนวนปมทั้งหมดในเน็ตเวิร์ก กราฟระดับ G_L สามารถสร้างได้จาก การค้นตามแนวกว้าง ในเวลา O(E) โดย E เป็นจำนวนเส้นเชื่อม และกระแสจำกัดการไหลในทุก ๆ กราฟระดับ จะสามารถหาได้ภายในเวลา O(VE)  ดังนั้นขั้นตอนวิธีของดีนิซจึงใช้เวลาในการทำงานเป็น O(V^2 E) 

นอกจากนี้ยังสามารถทำให้ขั้นตอนวิธีของดีนิซมีประสิทธิภาพเพิ่มขึ้นด้วยการใช้โครงสร้างข้อมูลที่เรียกว่า ต้นไม้พลวัต (dynamic trees) ซึ่งจะทำให้เวลาการหากระแสจำกัดการไหลลดลงเป็น O(E \log V) ทำให้ขั้นตอนวิธีโดยรวมใช้ทำงานเพียง O(VE \log V)

### กรณีพิเศษ
ในเน็ตเวิร์กที่มีความจุเอกลักษณ์ จะมีขอบเขตของเวลามากขึ้น แต่ละขั้นตอนการปิดกั้นการไหลสามารถพบได้ในเวลา O(E) และสามารถแสดงให้เห็นว่าจำนวนเฟสไม่เกิน O(\sqrt{E}) และ O(V^{2/3}) ดังนั้นขั้นตอนวิธีจะทำงานในเวลา O(\min\{V^{2/3}, E^{1/2}\}E) 

ในเน็ตเวิร์กที่เกิดจากปัญหาบบการจับคู่สองส่วน]] จำนวนเฟสจะถูกจำกัดด้วย O(\sqrt{V}) จึงนำไปสู่ขอบเขตเวลา O(\sqrt{V} E) ขั้นตอนวิธีที่ได้นั้นเรียกอีกอย่างว่าขั้นตอนวิธีฮอปครอฟต์-คาป โดยทั่วไป ขอบเขตนี้มีไว้สำหรับเน็ตเวิร์กเอกลักษณ์ใด ๆ — เครือข่ายที่จุดยอดแต่ละจุด ยกเว้นต้นทางและปลายทาง อาจมีวิถีของความจุขาเข้าเดียว หรือวิถีความจุของขาออกเดียว และความจุอื่นทั้งหมดเป็นจำนวนเต็มใด&nbsp;ๆ

## ตัวอย่าง
ให้ G เป็นเน็ตเวิร์กเริ่มต้น ซึ่งแต่ละเส้นเชื่อมจะมีขนาดของกระแสและความจุ G_L เป็นกราฟระดับ ปมที่มีเลขเป็นสีแดงคือค่าของ \operatorname{dist}(v) และวิถีสีน้ำเงินคือกระแสจำกัดการไหล

## ดูเพิ่ม
* ขั้นตอนวิธีของฟอร์ด-เฟอลเกอสัน
* ขั้นตอนวิธีของเอ็ดมอนด์-คาป

## เชิงอรรถ

## อ้างอิง

## บรรณานุกรม
* 
*  eISBN . .
* 

หมวดหมู่:ขั้นตอนวิธีกราฟ
หมวดหมู่:การไหลในเครือข่าย