Thuật toán Ford-Fulkerson

Mục lục

Các thuật ngữ được sử dụng
Thuật toán Ford-Fulkerson hoạt động như thế nào?
Ví dụ Ford-Fulkerson
Ví dụ về Python, Java và C / C ++
Ứng dụng Ford-Fulkerson

Trong hướng dẫn này, bạn sẽ tìm hiểu thuật toán Ford-Fulkerson là gì. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc về việc tìm luồng tối đa trong mạng luồng bằng C, C ++, Java và Python.

Thuật toán Ford-Fulkerson là một cách tiếp cận tham lam để tính toán lưu lượng tối đa có thể trong một mạng hoặc một đồ thị.

Một thuật ngữ, mạng dòng chảy , được sử dụng để mô tả một mạng lưới các đỉnh và cạnh với nguồn (S) và phần chìm (T). Mỗi đỉnh, ngoại trừ S và T , có thể nhận và gửi một lượng bằng nhau qua nó. S chỉ có thể gửi và T chỉ có thể nhận đồ.

Chúng ta có thể hình dung sự hiểu biết về thuật toán sử dụng dòng chất lỏng bên trong một mạng lưới các đường ống có công suất khác nhau. Mỗi đường ống có một dung tích chất lỏng nhất định mà nó có thể chuyển tại một thời điểm. Đối với thuật toán này, chúng ta sẽ tìm bao nhiêu chất lỏng có thể chảy từ nguồn đến bồn rửa tại một trường hợp sử dụng mạng.

Biểu đồ mạng luồng

Các thuật ngữ được sử dụng

Đường dẫn bổ sung

Nó là đường dẫn có sẵn trong mạng luồng.

Đồ thị dư

Nó đại diện cho mạng luồng có thêm luồng có thể.

Dung lượng dư

Nó là công suất của cạnh sau khi trừ lưu lượng từ công suất lớn nhất.

Thuật toán Ford-Fulkerson hoạt động như thế nào?

Thuật toán sau:

Khởi tạo luồng trong tất cả các cạnh thành 0.
Trong khi có một đường dẫn tăng cường giữa nguồn và bồn rửa, hãy thêm đường dẫn này vào luồng.
Cập nhật đồ thị phần dư.

Chúng ta cũng có thể xem xét đường đi ngược lại nếu được yêu cầu bởi vì nếu không xem xét chúng, chúng ta có thể không bao giờ tìm thấy luồng tối đa.

Các khái niệm trên có thể được hiểu với ví dụ dưới đây.

Ví dụ Ford-Fulkerson

Lưu lượng của tất cả các cạnh bằng 0 ở đầu.

Ví dụ về biểu đồ mạng luồng

Chọn bất kỳ đường đi tùy ý nào từ S đến T. Trong bước này, chúng ta đã chọn đường dẫn SABT. Tìm đường đi
Công suất nhỏ nhất trong ba cạnh là 2 (BT). Dựa trên cơ sở này, hãy cập nhật lưu lượng / dung lượng cho mỗi đường dẫn. Cập nhật năng lực
Chọn đường dẫn khác SDCT. Dung lượng tối thiểu giữa các cạnh này là 3 (SD). Tìm đường dẫn tiếp theo
Cập nhật dung lượng theo điều này. Cập nhật năng lực
Bây giờ, chúng ta hãy xem xét BD theo đường ngược lại. Chọn đường dẫn SABDCT. Công suất dư tối thiểu giữa các cạnh là 1 (DC). Tìm đường dẫn tiếp theo
Cập nhật dung lượng. Cập nhật các dung lượng
Dung lượng cho các đường chuyển tiếp và đảo ngược được xem xét riêng biệt.
Cộng tất cả các luồng = 2 + 3 + 1 = 6, là lưu lượng tối đa có thể có trên mạng luồng.

Lưu ý rằng nếu dung lượng cho bất kỳ cạnh nào đầy thì đường dẫn đó không thể được sử dụng.

Ví dụ về Python, Java và C / C ++

Python Java C C ++

 # Ford-Fulkerson algorith in Python from collections import defaultdict class Graph: def __init__(self, graph): self.graph = graph self. ROW = len(graph) # Using BFS as a searching algorithm def searching_algo_BFS(self, s, t, parent): visited = (False) * (self.ROW) queue = () queue.append(s) visited(s) = True while queue: u = queue.pop(0) for ind, val in enumerate(self.graph(u)): if visited(ind) == False and val> 0: queue.append(ind) visited(ind) = True parent(ind) = u return True if visited(t) else False # Applying fordfulkerson algorithm def ford_fulkerson(self, source, sink): parent = (-1) * (self.ROW) max_flow = 0 while self.searching_algo_BFS(source, sink, parent): path_flow = float("Inf") s = sink while(s != source): path_flow = min(path_flow, self.graph(parent(s))(s)) s = parent(s) # Adding the path flows max_flow += path_flow # Updating the residual values of edges v = sink while(v != source): u = parent(v) self.graph(u)(v) -= path_flow self.graph(v)(u) += path_flow v = parent(v) return max_flow graph = ((0, 8, 0, 0, 3, 0), (0, 0, 9, 0, 0, 0), (0, 0, 0, 0, 7, 2), (0, 0, 0, 0, 0, 5), (0, 0, 7, 4, 0, 0), (0, 0, 0, 0, 0, 0)) g = Graph(graph) source = 0 sink = 5 print("Max Flow: %d " % g.ford_fulkerson(source, sink))

 // Ford-Fulkerson algorith in Java import java.util.LinkedList; class FordFulkerson ( static final int V = 6; // Using BFS as a searching algorithm boolean bfs(int Graph()(), int s, int t, int p()) ( boolean visited() = new boolean(V); for (int i = 0; i < V; ++i) visited(i) = false; LinkedList queue = new LinkedList(); queue.add(s); visited(s) = true; p(s) = -1; while (queue.size() != 0) ( int u = queue.poll(); for (int v = 0; v 0) ( queue.add(v); p(v) = u; visited(v) = true; ) ) ) return (visited(t) == true); ) // Applying fordfulkerson algorithm int fordFulkerson(int graph()(), int s, int t) ( int u, v; int Graph()() = new int(V)(V); for (u = 0; u < V; u++) for (v = 0; v < V; v++) Graph(u)(v) = graph(u)(v); int p() = new int(V); int max_flow = 0; # Updating the residual calues of edges while (bfs(Graph, s, t, p)) ( int path_flow = Integer.MAX_VALUE; for (v = t; v != s; v = p(v)) ( u = p(v); path_flow = Math.min(path_flow, Graph(u)(v)); ) for (v = t; v != s; v = p(v)) ( u = p(v); Graph(u)(v) -= path_flow; Graph(v)(u) += path_flow; ) // Adding the path flows max_flow += path_flow; ) return max_flow; ) public static void main(String() args) throws java.lang.Exception ( int graph()() = new int()() ( ( 0, 8, 0, 0, 3, 0 ), ( 0, 0, 9, 0, 0, 0 ), ( 0, 0, 0, 0, 7, 2 ), ( 0, 0, 0, 0, 0, 5 ), ( 0, 0, 7, 4, 0, 0 ), ( 0, 0, 0, 0, 0, 0 ) ); FordFulkerson m = new FordFulkerson(); System.out.println("Max Flow: " + m.fordFulkerson(graph, 0, 5)); ) )

 / Ford - Fulkerson algorith in C #include #define A 0 #define B 1 #define C 2 #define MAX_NODES 1000 #define O 1000000000 int n; int e; int capacity(MAX_NODES)(MAX_NODES); int flow(MAX_NODES)(MAX_NODES); int color(MAX_NODES); int pred(MAX_NODES); int min(int x, int y) ( return x < y ? x : y; ) int head, tail; int q(MAX_NODES + 2); void enqueue(int x) ( q(tail) = x; tail++; color(x) = B; ) int dequeue() ( int x = q(head); head++; color(x) = C; return x; ) // Using BFS as a searching algorithm int bfs(int start, int target) ( int u, v; for (u = 0; u < n; u++) ( color(u) = A; ) head = tail = 0; enqueue(start); pred(start) = -1; while (head != tail) ( u = dequeue(); for (v = 0; v 0) ( enqueue(v); pred(v) = u; ) ) ) return color(target) == C; ) // Applying fordfulkerson algorithm int fordFulkerson(int source, int sink) ( int i, j, u; int max_flow = 0; for (i = 0; i < n; i++) ( for (j = 0; j = 0; u = pred(u)) ( increment = min(increment, capacity(pred(u))(u) - flow(pred(u))(u)); ) for (u = n - 1; pred(u)>= 0; u = pred(u)) ( flow(pred(u))(u) += increment; flow(u)(pred(u)) -= increment; ) // Adding the path flows max_flow += increment; ) return max_flow; ) int main() ( for (int i = 0; i < n; i++) ( for (int j = 0; j < n; j++) ( capacity(i)(j) = 0; ) ) n = 6; e = 7; capacity(0)(1) = 8; capacity(0)(4) = 3; capacity(1)(2) = 9; capacity(2)(4) = 7; capacity(2)(5) = 2; capacity(3)(5) = 5; capacity(4)(2) = 7; capacity(4)(3) = 4; int s = 0, t = 5; printf("Max Flow: %d", fordFulkerson(s, t)); )

 // Ford-Fulkerson algorith in C++ #include #include #include #include using namespace std; #define V 6 // Using BFS as a searching algorithm bool bfs(int rGraph(V)(V), int s, int t, int parent()) ( bool visited(V); memset(visited, 0, sizeof(visited)); queue q; q.push(s); visited(s) = true; parent(s) = -1; while (!q.empty()) ( int u = q.front(); q.pop(); for (int v = 0; v 0) ( q.push(v); parent(v) = u; visited(v) = true; ) ) ) return (visited(t) == true); ) // Applying fordfulkerson algorithm int fordFulkerson(int graph(V)(V), int s, int t) ( int u, v; int rGraph(V)(V); for (u = 0; u < V; u++) for (v = 0; v < V; v++) rGraph(u)(v) = graph(u)(v); int parent(V); int max_flow = 0; // Updating the residual values of edges while (bfs(rGraph, s, t, parent)) ( int path_flow = INT_MAX; for (v = t; v != s; v = parent(v)) ( u = parent(v); path_flow = min(path_flow, rGraph(u)(v)); ) for (v = t; v != s; v = parent(v)) ( u = parent(v); rGraph(u)(v) -= path_flow; rGraph(v)(u) += path_flow; ) // Adding the path flows max_flow += path_flow; ) return max_flow; ) int main() ( int graph(V)(V) = ((0, 8, 0, 0, 3, 0), (0, 0, 9, 0, 0, 0), (0, 0, 0, 0, 7, 2), (0, 0, 0, 0, 0, 5), (0, 0, 7, 4, 0, 0), (0, 0, 0, 0, 0, 0)); cout << "Max Flow: " << fordFulkerson(graph, 0, 5) << endl; )