ขั้นตอนวิธีของเอ็ดมอนด์-คาป

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

ขั้นตอนวิธี

ขั้นตอนวิธีนี้เหมือน ยกเว้นในส่วนของ (อังกฤษ: Augmenting path) การค้นหาวิถีเพิ่มพูนในขั้นตอนวิธีนี้นั้น เราจะหาจากวิถีสั่นสุดที่ยังเหลือที่ว่างให้ไหลไปได้ด้วยการค้นทางกว้าง โดยให้แต่ละวิถีมีน้ำหนักของมันเอง โดยจะใช้เวลาทั้งหมดประมาณ ${\displaystyle O(VE^{2})}$ ซึ่งคำนวณจากการที่สามารถหาวิถีเพิ่มพูนในแต่ละครั้งได้ในเวลา ${\displaystyle O(E)}$ ซึ่งในการทำงานแต่ละรอบนั้นจะต้องมีวิถีที่อิ่มตัว (Saturated edge) เกิดขึ้นอีกอย่างน้อย 1 วิถี จากขั้นตอนวิธีดังกล่าวจะส่งผลให้ระยะทางจากต้นกำเนิดถึงวิถีอิ่มตัวล่าสุดจะต้องมากกว่าเดิมเสมอ จากขั้นตอนวิธีดังกล่าวเราพบว่าระยะทางของวิถีเพิ่มพูนสั้นสุดนั้นเติบโตขึ้นเป็นลำดับทางเดียว โดยอ้างอิงจากบทพิสูจน์ดังนี้

รหัสเทียม

สามารถดูรายละเอียดเชิงลึกได้ที่ขั้นตอนวิธีของฟอร์ด-ฟูเกอร์สัน

algorithm EdmondsKarp

 ข้อมูลนำเข้า: C[1..n, 1..n]  (เมตริกความจุ)  E[1..n, 1..?]  (รายการผมเพื่อนบ้าน)  s  (ก๊อก)  t  (อ่าง)  ข้อมูลนำออก: f  (ค่าอัตราการไหลสูงสุด)  F  (เมตริกซึ่งแสดงค่าอัตราการไหลสูงสุดในแต่ละวิถึ)  f := 0  (กำหนดค่าเริ่มต้นให้อัตราการไหล)  F := array (1..n, 1..n)  (ค่าความจุที่เหลือ จาก u ไป v หรือ C[u,v] - F[u,v])  forever m, P := BreadthFirstSearch (C, E, s, t) if m = 0 break f := f + m  (การค้นแบบBacktrack และ สร้างวิถีการไหล)  v := t while v ≠ s u := P[v] F[u,v] := F[u,v] + m F[v,u] := F[v,u] - m v := u return (f, F) 

ขั้นตอนวิธี ค้นทางกว้าง (BreadthFirstSearch) ข้อมูลนำเข้า: C, E, s, t 'ข้อมูลนำออก: M[t]  (ความจุของวิถีที่พบ)  P  (ตารางบรรพบุรุษ)  P := array (1..n) for u in 1..n P[u] := -1 P[s] := -2  (ตรวจสอบว่าก๊อกนี้ไม่ถูกค้นพบซ้ำ)  M := array (1..n)  (ค่าความจุระหว่างวิถีที่ถูกค้นพบกับปม)  M[s] := ∞ Q := queue () Q.push (s) while Q.size () > 0 u := Q.pop () for v in E[u]  (ถ้ายังมีความจุให้ไหลได้ และ v ยังไม่เคยถูกค้นพบมาก่อน)  if C[u,v] - F[u,v] > 0 and P[v] = -1 P[v] := u M[v] := min (M[u], C[u,v] - F[u,v]) if v ≠ t Q.push (v) else return M[t], P return 0, P 

ตัวอย่าง

กำหนดให้เครือข่ายมี 7 ปม โดยมีจุดเริ่มต้นก๊อก A และ จบที่อ่าง G และ ความจุ ดังแสดงตามภาพด้านล่าง

ในทุกคู่ ${\displaystyle f/c}$ ที่ถูกเขียนบนวิถี ${\displaystyle f}$ และ ${\displaystyle c}$ คือ อัตราการไหลในปัจจุบัน และ ความจุของวิถีนั้น ตามลำดับ ค่าความจุที่เหลืออยู่จาก ${\displaystyle u}$ ไป ${\displaystyle v}$ คือ ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$ ส่วนต่างของค่าความจุของวิถีนั้นและอัตราการไหลที่ไหลผ่านวิถีดังกล่าว

ความจุ	วิถี
	ผลลัพธ์ในระบบ
${\displaystyle \min(c_{f}(A,D),c_{f}(D,E),c_{f}(E,G))=}$ ${\displaystyle \min(3-0,2-0,1-0)=}$ ${\displaystyle \min(3,2,1)=1}$	${\displaystyle A,D,E,G}$
${\displaystyle \min(c_{f}(A,D),c_{f}(D,F),c_{f}(F,G))=}$ ${\displaystyle \min(3-1,6-0,9-0)=}$ ${\displaystyle \min(2,6,9)=2}$	${\displaystyle A,D,F,G}$
${\displaystyle \min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D),c_{f}(D,F),c_{f}(F,G))=}$ ${\displaystyle \min(3-0,4-0,1-0,6-2,9-2)=}$ ${\displaystyle \min(3,4,1,4,7)=1}$	${\displaystyle A,B,C,D,F,G}$
${\displaystyle \min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,E),c_{f}(E,D),c_{f}(D,F),c_{f}(F,G))=}$ ${\displaystyle \min(3-1,4-1,2-0,0--1,6-3,9-3)=}$ ${\displaystyle \min(2,3,2,1,3,6)=1}$	${\displaystyle A,B,C,E,D,F,G}$

อ้างอิง

1. E. A. Dinic (1970). "Algorithm for solution of a problem of maximum flow in a network with power estimation". Soviet Math. Doklady (Doklady) 11: 1277–1280.
2. Jack Edmonds and Richard M. Karp (1972). "Theoretical improvements in algorithmic efficiency for network flow problems". Journal of the ACM 19 (2) : 248–264. doi:10.1145/321694.321699.
3. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001). "26.2". Introduction to Algorithms (second ed.). MIT Press and McGraw–Hill. pp. 660–663. .
4. Algorithms and Complexity (see pages 63-69). http://www.cis.upenn.edu/~wilf/AlgComp3.html 2006-10-05 ที่ เวย์แบ็กแมชชีน