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

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

## ขั้นตอนวิธี

ขั้นตอนวิธีนี้เหมือนขั้นตอนวิธีของฟอร์ด-ฟูเกอร์สัน ยกเว้นในส่วนของการค้นหาวิถีเพิ่มพูน () การค้นหาวิถีเพิ่มพูนในขั้นตอนวิธีนี้นั้น เราจะหาจากวิถีสั่นสุดที่ยังเหลือที่ว่างให้ไหลไปได้ด้วยการค้นทางกว้าง โดยให้แต่ละวิถีมีน้ำหนักของมันเอง โดยจะใช้เวลาทั้งหมดประมาณ O(V E^2) ซึ่งคำนวณจากการที่สามารถหาวิถีเพิ่มพูนในแต่ละครั้งได้ในเวลา 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 และ ความจุ ดังแสดงตามภาพด้านล่าง

300px

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

## อ้างอิง
# 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.
# 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.
# 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. ISBN 0-262-53196-8.
# Algorithms and Complexity (see pages 63-69). http://www.cis.upenn.edu/~wilf/AlgComp3.html 

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