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

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

ประสิทธิภาพ

ประสิทธิภาพของขั้นตอนวิธีนี้คือ O(EV) อย่างไรก็ตาม ขั้นตอนวิธีของทาร์จานนั้นมีประสิทธิภาพดีกว่า โดยมีประสิทธิภาพอยู่ที่ O(ElogV) สำหรับกราฟเบาบาง และ O(V²) สำหรับกราฟหนาแน่น โดยที่วิธีดังกล่าวนั้นมีประสิทธิภาพที่ใกล้เคียงกับขั้นตอนวิธีของพริม ในการหาต้นไม้แผ่ทั่วที่น้อยที่สุด และในปี พ.ศ.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 ออก

อ้างอิง

เพิ่มเติม

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