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

เราสามารถนำปัญหานี้มาเขียนให้อยู่ในรูปของทฤษฎีกราฟได้ โดยการแปลงปัญหาดังกล่าวเป็น กราฟมีทิศทาง (directed graph) ที่ทุกๆเส้นเชื่อม (ท่อน้ำ) จะมีน้ำหนักเป็น ความจุ c (ขนาดของท่อน้ำ) รวมทั้งกราฟจะประกอบด้วยปมต้นทาง X (ต้นน้ำ) และปมปลายทาง Y (อ่างน้ำที่เป็นปลายทางของน้ำ) นอกจากนี้ยังมีค่าพิเศษคือค่าการไหลของเส้นเชื่อม f กำกับในเส้นเชื่อม ซึ่งค่า f<=c สำหรับทุกเส้นเชื่อม และผลรวมของการไหล f จากเส้นเชื่อมใดๆที่เข้าสู่ปมจะมีค่าเท่ากับผลรวมของการไหล f จากเส้นเชื่อมที่ออกจากปมนั้นๆ เป้าหมายที่เราต้องการคือการหาผลรวมที่มากที่สุดที่เป็นไปได้ของการไหล f ที่ออกจากปมต้นทาง (โดยค่านั้นจะเท่ากับผลรวมของการไหล f ที่เข้าสู่ปมปลายทางด้วยเช่นกัน)

สำหรับอัลกอรึทึม จะนิยามถึงคำสองคำที่จะใช้ในการอธิบาย

  1. เครือข่ายตกค้าง (residual network) คือ เครือข่ายที่มีปมเหมือนเครือข่ายดั้งเดิม และเส้นเชื่อมแต่ละเส้นในเครือข่ายดั้งเดิมจะถูกแทนที่ด้วยเส้นเชื่อมใหม่จำนวนหนึ่งหรือสองเส้นเชื่อม โดยถ้าการไหลของเส้นเชื่อมที่เชื่อมปม x ไปยังปม y (x-y) มีค่าน้อยกว่าความจุ เส้นเชื่อมใหม่เส้นหนึ่งจะเป็นเส้นเชื่อมที่มีทิศเดิมจากปม x ไปยังปม y (x-y) โดยความจุของเส้นเชื่อมใหม่เส้นนี้จะมีค่าเท่ากับผลต่างของความจุและการไหล (เรียกว่า ความจุคงเหลือ (resident capacity)) และถ้าหากการไหลมีค่าไม่เป็น 0 แล้วจะมีเส้นเชื่อมใหม่อีกเส้นหนึ่งมีทิศย้อนกลับ คือจากปม y ไปยังปม x (y-x) โดยความจุของเส้นเชื่อมนี้จะเท่ากับค่าการไหลของ x-y
  2. วิถีแต่งเติม (augmenting path) คือ วิถีจากปมต้นทางถึงปมปลายทางในเครือข่ายตกค้าง (residual network) ที่ทำให้เพิ่มปริมาณการไหลในเครือข่ายให้มากขึ้น ข้อสำคัญของวิถีแต่งเติมนี้คือวิถีนั้นจะสามารถมีท่อน้ำที่ใช้ผิดทางไปจากเครือข่ายดั้งเดิมได้ โดยความจุของวิถีจะเท่ากับความจุของเส้นเชื่อมซึ่งมีความจุที่น้อยที่สุด

หลักการทำงานของขั้นตอนวิธี

  • เริ่มต้นการทำงานด้วยกราฟที่ไม่เกิดการไหลใดๆในเครือข่ายเลย
  • จากนั้นจะทำการเพิ่มปริมาณการไหลในเครือข่ายขึ้นเรื่อยๆ ตราบใดก็ตามที่ยังมีวิถีแต่งเติมจากปมต้นทางไปยังปมปลายทางในเครือข่ายตกค้าง

ใกล้เคียง