ขั้นตอนวิธีของเอ็ดมอนส์

ในเรื่องทฤษฎีกราฟ ขั้นตอนวิธีของเอ็ดมอนส์เป็นขั้นตอนวิธีที่ใช้ในการหาการแตกกิ่งที่ต่ำที่สุด หรือสูงที่สุด เมื่อจุดยอดถูกเชื่อมด้วยเส้นเชื่อมถ่วงน้ำหนักแบบมีทิศทาง ขั้นตอนวิธีการหาต้นไม้ทอดข้ามต่ำสุดจึงไม่สามารถนำมาใช้ได้ ดังนั้นจึงต้องใช้ขั้นตอนวิธีการหาการแตกกิ่งต่ำสุด ซึ่งขั้นตอนวิธีนี้ถูกเสนอโดย Yoeng-jin Chu และ Tseng-hong Liu ในปี พ.ศ. 2508 และหลังจากนั้น Edmonds ได้เสนอขั้นตอนวิธีเดียวกันในปี พ.ศ. 2510 ในการหาเส้นทางที่ยาวที่สุด เริ่มจากการหาเส้นเชื่อมที่ถ่วงน้ำหนักมากสุด และรอง ๆ มา ตามลำดับ แต่ถ้าเส้นเชื่อมนั้นสร้างวงวนจะถูกลบทิ้ง ในทางกลับกลันระยะทางที่สั้นที่สุดจะสามารถหาได้โดยการหาเส้นเชื่อมถ่วงน้ำหนักต่ำที่สุดก่อน สำหรับกราฟแบบไม่มีทิศทาง เราจะใช้ขั้นตอนวิธีของครูสกาลในการหาต้นไม้แผ่ขยายต่ำสุด

 ประสิทธิภาพ 
ประสิทธิภาพของขั้นตอนวิธีนี้คือ O(EV) อย่างไรก็ตาม ขั้นตอนวิธีของทาร์จานนั้นมีประสิทธิภาพดีกว่า โดยมีประสิทธิภาพอยู่ที่ O(ElogV) สำหรับกราฟเบาบาง และ O(V2) สำหรับกราฟหนาแน่น โดยที่วิธีดังกล่าวนั้นมีประสิทธิภาพที่ใกล้เคียงกับขั้นตอนวิธีของพริม ในการหาต้นไม้แผ่ทั่วที่น้อยที่สุด และในปี พ.ศ.2529 Gabow Galil Spencer และ Tarjan ได้คิดค้นขั้นตอนที่เร็วกว่า โดยมีประสิทธิภาพอยู่ที่ O(E + VlogV)

 ขั้นตอนวิธี 
 1. ลบทุกๆเส้นเชื่อมที่มีทิศทางไปยังปมราก
 2. เลือกเส้นเชื่อมที่พุ่งเข้าปมในแต่ละปม โดยเลือกเส้นที่มีน้ำหนักน้อยสุด
 3. แต่ละวงจรประกอบด้วย
 :* เส้นเชื่อม m ซึ่งเป็นเส้นเชื่อมในวงจรที่มีน้ำหนักน้อยสุด
 :* เชื่อมทุกปมในวงจรด้วยปมเทียม k ซึ่งเป็นปมที่สมมติขึ้นมา
 :* แต่ละเส้นเชื่อม e ที่มีทิศทางสู่ปม k ของกราฟเดิมนั้นจะต้อง
 - มีเส้นเชื่อม n เข้าสู่ปม k ในวงจร
 - สร้างทางเดินเชื่อมระหว่างเส้นเชื่อม e โดยให้ทางเดินนั้นมีผลรวมน้ำหนักของเส้นเชื่อมน้อยที่สุด ตามสมการ modWeight = weight("e") - ( weight("n") - weight("m") )
 4. เพิ่มเส้นเชื่อม e แล้วลบเส้นเชื่อม n ออก

 อ้างอิง 
 AlgoWiki AlgoWiki - Edmond's Algorithm
 การออกแบบและวิเคราะห์อัลกอริทึม (สมชาย ประสิทธิ์จูตระกูล)

 เพิ่มเติม 
 Implementation of Edmonds's optimum branching algorithm written in C++
 AlgoWiki - Edmond's Algotithm - A public-domain implementation of Edmonds's algorithm written in JAVA

หมวดหมู่:ขั้นตอนวิธีกราฟ