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

ขั้นตอนวิธีของดีนิซ (อังกฤษ: Dinic's algorithm) เป็นขั้นตอนวิธีสำหรับการแก้ปัญหาหาการไหลมากสุด (อังกฤษ: Maximum flow) ในระบบเครือข่ายการไหล (อังกฤษ: Flow network) ถูกคิดขึ้นโดยเยฟิม ดีนิทซ์ (อังกฤษ: Yefim Dinitz) นักวิทยาศาสตร์คอมพิวเตอร์ชาวยิว (อดีตเป็นชาวรัสเซีย) ในปี ค.ศ. 1970 ขั้นตอนวิธีนี้จะใกล้เคียงกับขั้นตอนวิธีของเอ็ดมอนด์-คาป (อังกฤษ: Edmonds-Karp algorithm) ซึ่งใช้หลักการหาวิถีสั้นสุดและมีอัตราการเติบโตเป็นของเวลาทำงาน $O(VE^2)$ แต่ขั้นตอนวิธีของดีนิซจะมีอัตราการเติบโตที่น้อยกว่าคือ $O(V^2E)$ ซึ่งเป็นผลมาจากการนำแนวคิดเรื่อง กราฟระดับ และ กระแสที่จำกัดการไหล มาใช้

นิยาม

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

กราฟความจุคงเหลิอ (residual capacity) เป็นกราฟที่ได้จาก $c_f : V\times V \to R^+$ นิยามโดย

1. เมื่อ $(u,v)\in E$,

   $c_f(u,v) = c(u,v) - f(u,v)$

   $c_f(v,u) = f(u,v)$

2. นอกเหนือจากนี้ $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) < c_f|_{E_L}(u,v)\}$และไม่มีวิถี $s-t$

ขั้นตอนวิธี

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

อินพุท: เน็ตเวิร์ค $G = ((V, E), c, s, t)$.

เอาต์พุต: กระแส $s-t$ ที่มีค่ากระแสสูงสุด $f$

1. กำหนด$f(e) = 0$ สำหรับทุก $e\in E$.
2. สร้าง $G_L$ จาก $G_f$ ของ $G$ ถ้า $\operatorname{dist}(t) = \infty$ ให้หยุดและคืนค่า $f$.
3. หากระแสจำกัดการไหล $f\;'$ ใน $G_L$.
4. ขยายกระแส$\ f$ ด้วย $f\;'$ จากนั้นกลับไปทำขั้นตอนที่ 2

วิเคราะห์

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

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

ตัวอย่าง

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

	$G$	$G_f$	$G_L$
1.
	กระแสจำกัดการไหลได้แก่ $\{s, 1, 3, t\}$ ด้วยกระแสขนาด 4 หน่วย $\{s, 1, 4, t\}$ ด้วยกระแสขนาด 6 หน่วย และ $\{s, 2, 4, t\}$ ด้วยกระแสขนาด 4 หน่วย ดังนั้นกระแสจำกัดการไหลมีทั้งหมด 14 หน่วย และ กระแส $|f|$ ทีค่าเท่ากับ 14 หมายเหตุ จะเห็นว่าทุก ๆ วิถีแต่งเติม ในกระแสจำกัดการไหลจะมี 3 เส้นเชื่อม
2.
	กระแสจำกัดการไหลได้แก่ $\{s, 2, 4, 3, t\}$ ด้วยกระแสขนาด 5 หน่วย ดังนั้นกระแสจำกัดการไหลมีทั้งหมด 5 หน่วย และ กระแส $|f|$ ทีค่าเท่ากับ 14+5=19 หมายเหตุ จะเห็นว่าทุก ๆ วิถีแต่งเติม ในกระแสจำกัดการไหลจะมี 4 เส้นเชื่อม
3.
	จะเห็นว่าในกราฟ $G_f$ ไม่มีวิถีที่จะไปถึง $t$ ได้แล้ว ขั้นตอนวิธีก็จะจบลงและคืนค่ากระแสที่มีค่าสูงสุดนั้นก็คือ 19 หมายเหตุ จะเห็นว่าจำนวนเส้นเชื่อมในวิถีแต่งเติมจะเพิ่มขึ้นอย่างน้อย 1 ในทุก ๆ ครั้งที่หากระแสจำกัดการไหล

ดูเพิ่ม

• Ford–Fulkerson algorithm
• Maximum flow problem
• ขั้นตอนวิธีของเอ็ดมอนด์-คาป

บรรณานุกรม

• Yefim Dinitz (2006). "Dinitz' Algorithm: The Original Version and Even's Version". In Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman. Theoretical Computer Science: Essays in Memory of Shimon Even. Springer. pp. 218–240. ISBN 978-3540328803. http://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf. 
• Tarjan, R. E. (1983). Data structures and network algorithms. 
• B. H. Korte, Jens Vygen (2008). "8.4 Blocking Flows and Fujishige's Algorithm". Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics, 21). Springer Berlin Heidelberg. pp. 174–176. ISBN 978-3-540-71844-4.