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

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

นิยาม

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

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

1. เมื่อ ${\displaystyle (u,v)\in E}$ ,
2. : ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$ 
3. : ${\displaystyle c_{f}(v,u)=f(u,v)}$ 
4. นอกเหนือจากนี้ ${\displaystyle c_{f}(u,v)=0}$ 

กราฟความจุคงเหลิอ คือกราฟ ${\displaystyle G_{f}=((V,E_{f}),c_{f}|_{E_{f}},s,t)}$  ที่มี

${\displaystyle E_{f}=\{(u,v)\in V\times V:c_{f}(u,v)>0\}}$ .

วิถีแต่งเติม (augmenting path) คือวิถีจาก ${\displaystyle s-t}$  ภายในกราฟความจุคงเหลิอ ${\displaystyle G_{f}}$ .

ให้ ${\displaystyle \operatorname {dist} (v)}$  แทนวิถีสั้นสุดจาก ${\displaystyle s}$  ไป ${\displaystyle v}$  ในกราฟ ${\displaystyle G_{f}}$ 

จะได้ว่า กราฟระดับ (level graph) ของ ${\displaystyle G_{f}}$  คือกราฟ ${\displaystyle G_{L}=(V,E_{L},c_{f}|_{E_{L}},s,t)}$  ที่มี

${\displaystyle E_{L}=\{(u,v)\in E_{f}:\operatorname {dist} (v)=\operatorname {dist} (u)+1\}}$ .

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

ขั้นตอนวิธี

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

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

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

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

วิเคราะห์

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

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

ตัวอย่าง

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

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

ดูเพิ่ม

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

บรรณานุกรม

• Yefim Dinitz (2006). "Dinitz' Algorithm: The Original Version and Even's Version". ใน Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman (บ.ก.). Theoretical Computer Science: Essays in Memory of [[Shimon Even]] (PDF). Springer. pp. 218–240. ISBN 978-3540328803. URL–wikilink conflict (help)CS1 maint: multiple names: editors list (link)
• Tarjan, R. E. (1983). Data structures and network algorithms.CS1 maint: ref=harv (link)
• 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.