อัลกอริทึมฟอร์ด-ฟูลเลอร์สัน (Ford-Fulkerson Algorithm)

อัลกอริทึมฟอร์ด-ฟูลเลอร์สัน (Ford-Fulkerson) ใช้หา Maximum Flow จากโหนดต้นทาง (Source) ไปยังโหนดปลายทาง (Sink) ในกราฟที่มีความจุ (Capacity) บนเส้นเชื่อม

ข้อจำกัด:

• Flow บนเส้นเชื่อมไม่เกินความจุที่กำหนด
• Flow เข้าและ Flow ออกของโหนดกลางต้องเท่ากัน (ยกเว้น Source และ Sink)

การรับค่าและแสดงผล

Input: เมทริกซ์ตyacency (ความจุ)
0 10 0 10 0 0
0 0  4  2  8 0
0 0  0  0  0 10
0 0  0  0  9 0
0 0  6  0  0 10
0 0  0  0  0 0

Output: Maximum flow is: 19

อัลกอริทึม

bfs(vert, start, sink) - หา Augmenting Path ด้วย BFS

fordFulkerson(vert, source, sink) - คำนวณ Max Flow

Begin
  สร้าง Residual Graph คัดลอกจากกราฟต้นฉบับ
  
  while bfs(vert, source, sink) เป็น true do
    pathFlow := INF
    v := sink
    
    // หา bottleneck capacity
    while v != source do
      u := predecessor[v]
      pathFlow := min(pathFlow, residualGraph[u, v])
      v := predecessor[v]
    done
    
    // อัปเดต Residual Graph
    v := sink
    while v != source do
      u := predecessor[v]
      residualGraph[u,v] -= pathFlow
      residualGraph[v,u] += pathFlow
      v := predecessor[v]
    done
    
    maxFlow := maxFlow + pathFlow
  done
  
  return maxFlow
End

ตัวอย่างโค้ด (C++)

#include <iostream>
#include <queue>
#define NODE 6
using namespace std;

typedef struct { int val, state, pred; } node;

int graph[NODE][NODE] = {
  {0, 10, 0, 10, 0, 0},
  {0, 0, 4, 2, 8, 0},
  {0, 0, 0, 0, 0, 10},
  {0, 0, 0, 0, 9, 0},
  {0, 0, 6, 0, 0, 10},
  {0, 0, 0, 0, 0, 0}
};

int resGraph[NODE][NODE];

bool bfs(node *vert, node start, node sink) {
  queue<node> que;
  for(int i = 0; i < NODE; i++) vert[i].state = 0;
  vert[start.val].state = 1;
  vert[start.val].pred = -1;
  que.push(start);
  
  while(!que.empty()) {
    node u = que.front(); que.pop();
    for(int i = 0; i < NODE; i++)
      if(resGraph[u.val][i] > 0 && vert[i].state == 0) {
        que.push(vert[i]);
        vert[i].pred = u.val;
        vert[i].state = 1;
      }
  }
  return (vert[sink.val].state == 1);
}

int fordFulkerson(node *vert, node source, node sink) {
  int maxFlow = 0;
  
  for(int i = 0; i < NODE; i++)
    for(int j = 0; j < NODE; j++)
      resGraph[i][j] = graph[i][j];
  
  while(bfs(vert, source, sink)) {
    int pathFlow = 999;
    for(int v = sink.val; v != source.val; v = vert[v].pred) {
      int u = vert[v].pred;
      pathFlow = min(pathFlow, resGraph[u][v]);
    }
    
    for(int v = sink.val; v != source.val; v = vert[v].pred) {
      int u = vert[v].pred;
      resGraph[u][v] -= pathFlow;
      resGraph[v][u] += pathFlow;
    }
    
    maxFlow += pathFlow;
  }
  return maxFlow;
}

int main() {
  node vertices[NODE], source, sink;
  for(int i = 0; i < NODE; i++) vertices[i].val = i;
  source.val = 0; sink.val = 5;
  
  cout << "Maximum flow is: " << fordFulkerson(vertices, source, sink);
}

ผลลัพธ์

Maximum flow is: 19