อัลกอริทึมของ Dinicหรืออัลกอริทึมของ Dinitzเป็น อัลกอริทึม พหุนามที่แข็งแกร่งสำหรับการคำนวณการไหลสูงสุดในเครือข่ายการไหลซึ่งคิดค้นขึ้นในปี 1970 โดยนักวิทยาศาสตร์คอมพิวเตอร์ชาวอิสราเอล (อดีตสหภาพโซเวียต) Yefim Dinitz [ ^{1 ] อั}ลกอริทึมทำงานใน${\displaystyle O(|V|^{2}|E|)}$เวลาและคล้ายกับอัลกอริทึม Edmonds–Karpซึ่งทำงานใน${\displaystyle O(|V||E|^{2})}$ข้อดีของอัลกอริธึมของ Dinic คือใช้เส้นทางเสริมที่สั้นที่สุด การนำแนวคิดของกราฟระดับและการไหลที่ถูกปิดกั้นมาใช้ทำให้อัลกอริธึมของ Dinic สามารถทำงานได้อย่างมีประสิทธิภาพ

Dinitz คิดค้นอัลกอริทึมนี้ในเดือนมกราคม พ.ศ. 2512 ขณะเป็นนักศึกษาปริญญาโทในกลุ่มของGeorgy Adelson-Velsky ไม่กี่ทศวรรษต่อมา เขาจะเล่าว่า: ^{[ 2 ]}

ในชั้นเรียนวิชาอัลกอริธึมของ Adel'son-Vel'sky อาจารย์ผู้สอนมีนิสัยชอบให้โจทย์ที่จะอภิปรายในครั้งต่อไปเป็นแบบฝึกหัดแก่นักเรียน อัลกอริทึม DA ถูกคิดค้นขึ้นเพื่อตอบสนองต่อแบบฝึกหัดดังกล่าว ในขณะนั้น ผู้คิดค้นยังไม่ทราบข้อเท็จจริงพื้นฐานเกี่ยวกับ [ อัลกอริทึม Ford–Fulkerson ]…

⋮ บางครั้งความไม่รู้ก็มีข้อดี เป็นไปได้มากว่า DA จะไม่ถูกคิดค้นขึ้นมาหากผู้เขียนรู้ถึงความเป็นไปได้ของการลดความอิ่มตัวของขอบภาพ

ในปี 1970 Dinitz ได้ตีพิมพ์คำอธิบายของอัลกอริทึมในDoklady Akademii Nauk SSSRในปี 1974 Shimon Evenและ (นักศึกษาปริญญาเอกของเขาในขณะนั้น) Alon Itai ที่Technionใน Haifa ต่างก็สงสัยและสนใจอัลกอริทึมของ Dinitz รวมถึง แนวคิดที่เกี่ยวข้องของ Alexander V. Karzanovเกี่ยวกับการปิดกั้นการไหล อย่างไรก็ตาม พวกเขาพบว่าการถอดรหัสเอกสารทั้งสองฉบับนั้นยาก เนื่องจากแต่ละฉบับจำกัดไว้ที่สี่หน้าเพื่อให้เป็นไปตามข้อจำกัดของวารสารDoklady Akademii Nauk SSSR Even ไม่ยอมแพ้ และหลังจากพยายามสามวัน เขาก็สามารถเข้าใจเอกสารทั้งสองฉบับได้ ยกเว้นปัญหาการบำรุงรักษาเครือข่ายแบบเลเยอร์ ในช่วงสองสามปีต่อมา Even ได้บรรยายเกี่ยวกับ "อัลกอริทึมของ Dinic" โดยออกเสียงชื่อผู้เขียนผิดในขณะที่เผยแพร่อัลกอริทึมนี้ Even และ Itai ยังได้มีส่วนร่วมในอัลกอริทึมนี้โดยการรวมBFSและDFSซึ่งเป็นวิธีการนำเสนออัลกอริทึมที่ใช้กันทั่วไปในปัจจุบัน^{[ 2 ]}

เป็นเวลากว่า 10 ปีหลังจากที่คิดค้นอัลกอริทึม Ford–Fulkerson ขึ้นมา ก็ยังไม่มีใครทราบว่าอัลกอริทึมนี้จะสามารถทำงานได้ในเวลาพหุนามในกรณีทั่วไปที่มีความจุของขอบเป็นจำนวนอตรรกยะหรือไม่ นี่จึงเป็นสาเหตุที่ทำให้ไม่มีอัลกอริทึมใดที่สามารถแก้ปัญหาการไหลสูงสุดในกรณีทั่วไปได้ในเวลาพหุนาม อัลกอริทึมของ Dinitz และอัลกอริทึม Edmonds–Karp (ตีพิมพ์ในปี 1972) ต่างก็แสดงให้เห็นโดยอิสระว่า ในอัลกอริทึม Ford–Fulkerson ถ้าเส้นทางเสริมแต่ละเส้นเป็นเส้นทางที่สั้นที่สุด ความยาวของเส้นทางเสริมจะไม่ลดลง และอัลกอริทึมจะสิ้นสุดลงเสมอ

อนุญาต${\displaystyle G=((V,E),c,f,s,t)}$เป็นเครือข่ายกับ${\displaystyle c(u,v)}$และ${\displaystyle f(u,v)}$ความจุและการไหลของขอบ${\displaystyle (u,v)}$ตามลำดับ

ความจุคงเหลือคือการแมป${\displaystyle c_{f}\colon V\times V\to R^{+}}$กำหนดไว้ดังนี้

1. ถ้า${\displaystyle (u,v)\in E}$,

   ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$

2. ถ้า${\displaystyle (v,u)\in E}$,

   ${\displaystyle c_{f}(u,v)=f(v,u)}$

3. ${\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\colon \;c_{f}(u,v)>0\}}$.

เส้นทางเสริมคือ${\displaystyle s}$–${\displaystyle t}$เส้นทางในกราฟส่วนเหลือ${\displaystyle G_{f}}$.

กำหนด${\displaystyle \operatorname {dist} (v)}$ให้เป็นความยาวของเส้นทางที่สั้นที่สุดจาก${\displaystyle s}$ถึง${\displaystyle v}$ใน${\displaystyle G_{f}}$จากนั้นกราฟระดับของ${\displaystyle G_{f}}$คือกราฟ${\displaystyle G_{L}=((V,E_{L}),c_{f}|_{E_{L}},s,t)}$, ที่ไหน

${\displaystyle E_{L}=\{(u,v)\in E_{f}\colon \;\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)\colon \;f'(u,v)<c_{f}|_{E_{L}}(u,v)\}}$ไม่มี${\displaystyle s}$–${\displaystyle t}$เส้นทาง^{[หมายเหตุ 1 ] [ 3 ]}

อัลกอริทึมของ Dinic

อินพุต : เครือข่าย${\displaystyle G=((V,E),c,s,t)}$.

ผลลัพธ์ : แอน${\displaystyle s}$–${\displaystyle 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 ชั้นในแต่ละครั้ง ดังนั้นจึงมีจำนวนชั้นอย่างมากที่สุด${\displaystyle |V|-1}$การปิดกั้นการไหลในอัลกอริทึม สำหรับแต่ละกรณี:

• กราฟระดับ${\displaystyle G_{L}}$สามารถสร้างได้โดยใช้การค้นหาแบบกว้าง (breadth-first search ) ใน${\displaystyle O(E)}$เวลา
• การไหลที่ถูกปิดกั้นในกราฟระดับ${\displaystyle G_{L}}$สามารถพบได้ใน${\displaystyle O(VE)}$เวลา^{[หมายเหตุ 2 ]}

ด้วยระยะเวลาการวิ่งทั้งหมด${\displaystyle O(E+VE)=O(VE)}$สำหรับแต่ละชั้น ดังนั้น เวลาในการทำงานของอัลกอริทึมของ Dinic จึงเป็น${\displaystyle O(V^{2}E)}$[ ^{2 ]​}

การใช้โครงสร้างข้อมูลที่เรียกว่าต้นไม้แบบไดนามิกสามารถลดเวลาในการค้นหาสิ่งกีดขวางการไหลในแต่ละเฟสลงได้${\displaystyle O(E\log V)}$ดังนั้น เวลาในการทำงานของอัลกอริทึมของ Dinic จึงสามารถปรับปรุงให้ดีขึ้นได้${\displaystyle O(VE\log V)}$.

ต่อไปนี้เป็นการจำลองอัลกอริทึมของ Dinic ในกราฟระดับ${\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 t}$ไม่สามารถติดต่อได้ใน${\displaystyle G_{f}}$อัลกอริทึมจะสิ้นสุดการทำงานและส่งคืนค่าการไหลที่มีค่าสูงสุด 19 โปรดทราบว่าในแต่ละการไหลที่ถูกปิดกั้น จำนวนขอบในเส้นทางเสริมจะเพิ่มขึ้นอย่างน้อย 1

• อัลกอริทึมฟอร์ด-ฟุลเคอร์สัน
• ปัญหาการไหลสูงสุด