เมนูนำทาง
ขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน โปรแกรมตัวอย่างขั้นตอนวิธีสามารถเขียนอธิบายในรูปแบบของโปรแกรมตัวอย่างได้ ดังนี้
Algorithm Ford–Fulkerson input: กราฟ G ที่ต้องการหาค่าการไหลมากสุด พร้อมทั้งค่าความจุ C, ปมเริ่มต้น result=0 //ตั้งค่าผลลัพธ์เริ่มต้นให้เป็น 0 for each edge (u,v) in G f(u,v) = 0 //ตั้งค่าเริ่มต้นค่าการไหลของเส้นเชื่อมเป็น 0 ให้ทุกเส้นเชื่อมในกราฟ G while(true) P = findPath( ) //ทำการหาวิถีแต่งเติม (คำสั่ง findPath จะคืนวิถีแต่งเติมที่พบ) pathCapacity = min(c) in path P //ให้ pathCapacity เป็นค่าความจุที่น้อยสุดของค่าความจุ c ของทุกเส้นเชื่อมในวิถี P (ซึ่งก็คือปริมาณการไหลในวิถีนั้น) if (pathCapacity <= 0) exit while //ถ้าไม่สามารถหาวิถีแต่งเติมได้อีกแล้ว ให้หยุดการทำงานออกจากวงวน else result += pathCapacity //ผลลัพธ์ใหม่เท่ากับผลรวมของผลลัพธ์เดิมและความจุของวิถีแต่งเติม for each edge (u,v) in P //วนทำงานทุกเส้นเชื่อมในวิถี P เพื่อปรับปรุงเครือข่ายตกค้าง f(u,v) = f(u,v) + pathCapacity //เพิ่มค่าการไหลของเส้นเชื่อมให้กับเส้นเชื่อมที่มีทิศทางเดียวกับการไหลในวิถีแต่งเติม f(v,u) = f(v,u) - pathCapacity //เพิ่มค่าการไหลของเส้นเชื่อมให้กับเส้นเชื่อมที่มีทิศทางตรงข้ามกับการไหลในวิถีแต่งเติม end whilereturn result //คืนค่าผลลัพธ์ที่ต้องการ (ค่าการไหลมากสุด)
สำหรับขั้นตอนในการหาวิถีแต่งเติม (คำสั่ง findPath) สามารถนำไปเขียนใช้งานจริงได้หลากหลายวิธี
เมนูนำทาง
ขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน โปรแกรมตัวอย่างใกล้เคียง
แหล่งที่มา
WikiPedia: ขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน http://community.topcoder.com/tc?module=Static&d1=... http://aduni.org/courses/algorithms/courseware/han...