Thuật toán Ford-Fulkerson được dùng để phát hiện luồng cực đại từ đỉnh nguồn đến đỉnh hố (sink) trong một đồ thị cho trước. Trong đồ thị này, mỗi cạnh có dung lượng. Hai đỉnh được cung cấp tên là Source (nguồn) và Sink (hố). Đỉnh nguồn có tất cả cạnh ra, không có cạnh vào, và đỉnh hố sẽ có tất cả cạnh vào, không có cạnh ra.
Có một số ràng buộc:
- Luồng trên một cạnh không vượt quá dung lượng cho trước của cạnh đó.
- Luồng vào và luồng ra cũng sẽ bằng nhau cho mọi cạnh, trừ đỉnh nguồn và đỉnh hố.
Đầu vào và Đầu ra
Đầu vào: Ma trận kề: 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 Đầu ra: Luồng cực đại là: 19
Thuật toán
bfs(vert, start, sink)
Đầu vào: Danh sách đỉnh, nút bắt đầu, và nút hố.
Đầu ra: True khi nút hố được thăm.
Bắt đầu
ban đầu đánh dấu tất cả nút là chưa thăm
trạng thái của start là đã thăm
tiền nhiệm của nút bắt đầu là ∅
chèn start vào hàng đợi qu
trong khi qu không rỗng, thực hiện
xóa phần tử từ hàng đợi gán vào đỉnh u
với mọi đỉnh i trong đồ thị dư, thực hiện
nếu u và i kết nối, và i chưa thăm, thì
thêm đỉnh i vào hàng đợi
tiền nhiệm của i là u
đánh dấu i là đã thăm
kết thúc
kết thúc
kết thúc
trả về true nếu trạng thái của đỉnh hố là đã thăm
Kết thúc
fordFulkerson(vert, source, sink)
Đầu vào: Danh sách đỉnh, đỉnh nguồn, và đỉnh hố.
Đầu ra: Luồng cực đại từ nguồn đến hố.
Bắt đầu
tạo đồ thị dư và sao chép đồ thị cho trước vào nó
trong khi bfs(vert, source, sink) là true, thực hiện
pathFlow := ∞
v := đỉnh hố
trong khi v ≠ đỉnh bắt đầu, thực hiện
u := tiền nhiệm của v
pathFlow := minimum của pathFlow và residualGraph[u, v]
v := tiền nhiệm của v
kết thúc
v := đỉnh hố
trong khi v ≠ đỉnh bắt đầu, thực hiện
u := tiền nhiệm của v
residualGraph[u,v] := residualGraph[u,v] - pathFlow
residualGraph[v,u] := residualGraph[v,u] - pathFlow
v := tiền nhiệm của v
kết thúc
maxFlow := maxFlow + pathFlow
kết thúc
trả về maxFlow
Kết thúc
Ví dụ (C++)
#include <iostream>
#include <queue>
#define NODE 6
using namespace std;
typedef struct node {
int val;
int state; // trạng thái
int pred; // tiền nhiệm
} node;
int minimum(int a, int b) {
return (a < b) ? a : b;
}
int resGraph[NODE][NODE];
/* int graph[NODE][NODE] = {
{0, 16, 13, 0, 0, 0},
{0, 0, 10, 12, 0, 0},
{0, 4, 0, 0, 14, 0},
{0, 0, 9, 0, 0, 20},
{0, 0, 0, 7, 0, 4},
{0, 0, 0, 0, 0, 0}
}; */
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 bfs(node *vert, node start, node sink) {
node u;
int i, j;
queue<node> que;
for(i = 0; i < NODE; i++) {
vert[i].state = 0; // chưa thăm
}
vert[start.val].state = 1; // đã thăm
vert[start.val].pred = -1; // không có nút cha
que.push(start); // chèn nút bắt đầu
while(!que.empty()) {
u = que.front();
que.pop();
for(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;
int u, v;
for(int i = 0; i < NODE; i++) {
for(int j = 0; j < NODE; j++) {
resGraph[i][j] = graph[i][j]; // ban đầu đồ thị dư là đồ thị chính
}
}
while(bfs(vert, source, sink)) {
// tìm đường tăng luồng dùng BFS
int pathFlow = 999; // như vô cực
for(v = sink.val; v != source.val; v = vert[v].pred) {
u = vert[v].pred;
pathFlow = minimum(pathFlow, resGraph[u][v]);
}
for(v = sink.val; v != source.val; v = vert[v].pred) {
u = vert[v].pred;
resGraph[u][v] -= pathFlow; // cập nhật dung lượng dư của cạnh
resGraph[v][u] += pathFlow; // cập nhật dung lượng dư của cạnh ngược
}
maxFlow += pathFlow;
}
return maxFlow; // luồng cực đại tổng thể
}
int main() {
node vertices[NODE];
node source, sink;
for(int i = 0; i < NODE; i++) {
vertices[i].val = i;
}
source.val = 0;
sink.val = 5;
int maxFlow = fordFulkerson(vertices, source, sink);
cout << "Maximum flow is: " << maxFlow << endl;
}
Đầu ra
Maximum flow is: 19