ขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน

ขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน  เป็นขั้นตอนวิธีสำหรับแก้ปัญหาเรื่องการไหลมากสุด (maximum flow) ของการไหลในเครือข่าย (network flow) ซึ่งขั้นตอนวิธีนี้ถูกพัฒนาขึ้นโดย Lester Randolph Ford และ Delbert Ray Fulkerson ได้รับการตีพิมพ์เผยแพร่ในปี ค.ศ. 1956
อธิบายปัญหา.
ลักษณะของปัญหาการไหลมากสุด คือ เมื่อนำท่อน้ำจำนวนมากมาต่อกันในลักษณะของเครือข่าย (ปลายท่อหนึ่งด้านจะสามารถต่อกับปลายของท่ออื่น ๆ ได้มากกว่าหนึ่งท่อ) โดยท่อแต่ละส่วนมีขนาดพื้นที่หน้าตัดของท่อไม่เท่ากัน จะหาปริมาณน้ำที่มากที่สุดที่ไหลจากท่อเหล่านี้จากจุดเริ่มต้นถึงจุดสุดท้าย ณ เวลาหนึ่ง
ๆ
ข้อสังเกตที่สำคัญของปัญหา คือ ปริมาณน้ำที่เข้าปลายท่อด้านหนึ่ง จะต้องเท่ากับปริมาณน้ำที่ออกจากปลายท่ออีกปลายหนึ่งของท่อนั้น
แนวความคิดหลัก.
เราสามารถนำปัญหานี้มาเขียนให้อยู่ในรูปของทฤษฎีกราฟได้ โดยการแปลงปัญหาดังกล่าวเป็น กราฟมีทิศทาง (directed graph) ที่ทุก ๆ เส้นเชื่อม (ท่อน้ำ) จะมีน้ำหนักเป็น ความจุ c (ขนาดของท่อน้ำ) รวมทั้งกราฟจะประกอบด้วยปมต้นทาง X (ต้นน้ำ) และปมปลายทาง Y (อ่างน้ำที่เป็นปลายทางของน้ำ) นอกจากนี้ยังมีค่าพิเศษคือค่าการไหลของเส้นเชื่อม f กำกับในเส้นเชื่อม ซึ่งค่า f<=c สำหรับทุกเส้นเชื่อม และผลรวมของการไหล f จากเส้นเชื่อมใด ๆ ที่เข้าสู่ปมจะมีค่าเท่ากับผลรวมของการไหล f จากเส้นเชื่อมที่ออกจากปมนั้น ๆ เป้าหมายที่เราต้องการคือการหาผลรวมที่มากที่สุดที่เป็นไปได้ของการไหล f ที่ออกจากปมต้นทาง (โดยค่านั้นจะเท่ากับผลรวมของการไหล f ที่เข้าสู่ปมปลายทางด้วยเช่นกัน)
สำหรับอัลกอรึทึม จะนิยามถึงคำสองคำที่จะใช้ในการอธิบาย
โปรแกรมตัวอย่าง.
ขั้นตอนวิธีสามารถเขียนอธิบายในรูปแบบของโปรแกรมตัวอย่างได้ ดังนี้
 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 while
 return result "//คืนค่าผลลัพธ์ที่ต้องการ (ค่าการไหลมากสุด)"
สำหรับขั้นตอนในการหาวิถีแต่งเติม (คำสั่ง findPath) สามารถนำไปเขียนใช้งานจริงได้หลากหลายวิธี
ข้อจำกัด.
ขั้นตอนวิธีนี้จะสามารถรับประกันได้ว่าการทำงานดังกล่าวมีจุดสิ้นสุด ก็ต่อเมื่อ
ถ้าหากไม่เป็นไปตามเงื่อนไขดังกล่าว จะไม่สามารถรับประกันได้ว่าการทำงานมีจุดสิ้นสุด (อาจเกิดการการทำงานไปเรื่อย ๆ ไม่สามารถหาที่สิ้นสุดได้ ไม่สามารถใช้ในการหาคำตอบได้)
อย่างไรก็ตามหากเราใช้ ขั้นตอนวิธีของเอ็ดมอนด์-คาป จะสามารถแก้ไขข้อจำกัดดังกล่าวในขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สันได้
ประสิทธิภาพเชิงเวลา.
จะขึ้นกับวิธีที่ใช้ในการหาวิถีแต่งเติม
ปัญหาที่เกี่ยวข้อง.
นอกจากขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สันจะใช้ในการแก้ปัญหาการไหลมากสุดแล้ว สามารถนำไปใช้กับปัญหาอื่น ๆ ได้อีกมากมายที่มีพื้นฐานมาจากปัญหาการไหลมากสุด
ตัวอย่างเช่น