Giải thuật luồng cực đại (Maximum Flow Algorithm) là một phương pháp trong lý thuyết đồ thị được sử dụng để tìm luồng cực đại từ một đỉnh nguồn (source) đến một đỉnh đích (sink) trong một mạng lưới luồng. Một số giải thuật phổ biến để giải quyết bài toán này bao gồm:
1. Giải Thuật Ford-Fulkerson:
Giải thuật Ford-Fulkerson là một phương pháp cơ bản để tìm luồng cực đại trong một mạng lưới. Giải thuật này sử dụng phương pháp tìm kiếm theo chiều sâu (DFS) để tìm các đường tăng luồng từ nguồn đến đích. Cụ thể:
Khởi tạo: Bắt đầu với luồng bằng 0.
Tìm đường tăng: Sử dụng DFS hoặc BFS để tìm đường đi từ nguồn đến đích sao cho tất cả các cạnh trong đường đi đều có khả năng chấp nhận thêm luồng (còn thừa dung lượng).
Tăng luồng: Tăng luồng dọc theo đường đi vừa tìm được, sau đó cập nhật dung lượng của các cạnh trong đường đi này.
Lặp lại: Lặp lại quá trình tìm đường tăng và tăng luồng cho đến khi không còn đường tăng nào từ nguồn đến đích.
2. Giải Thuật Edmonds-Karp:
Giải thuật Edmonds-Karp là một phiên bản của giải thuật Ford-Fulkerson, nhưng thay vì sử dụng DFS, nó sử dụng BFS để tìm đường tăng. BFS đảm bảo rằng giải thuật tìm thấy đường tăng ngắn nhất (ít cạnh nhất) từ nguồn đến đích trong mỗi lần lặp. Điều này giúp cải thiện hiệu suất và đảm bảo giải thuật kết thúc trong thời gian đa thức.
3. Giải Thuật Dinic:
Giải thuật Dinic (hay Dinitz) là một giải thuật nâng cao khác cho bài toán luồng cực đại. Giải thuật này sử dụng khái niệm "level graph" và áp dụng phương pháp tìm đường tăng trong nhiều bước:
Khởi tạo: Khởi tạo luồng bằng 0.
Xây dựng Level Graph: Sử dụng BFS để xây dựng đồ thị mức (level graph) từ nguồn đến đích, trong đó mỗi đỉnh được gán một mức (level) thể hiện khoảng cách ngắn nhất từ nguồn.
Tìm đường tăng trong Level Graph: Sử dụng DFS để tìm tất cả các đường tăng trong đồ thị mức này.
Cập nhật Level Graph: Sau khi không còn đường tăng trong đồ thị mức hiện tại, xây dựng lại đồ thị mức mới và lặp lại quá trình.
4. Giải Thuật Push-Relabel:
Giải thuật Push-Relabel (còn gọi là Goldberg-Tarjan) là một phương pháp khác để giải bài toán luồng cực đại. Thay vì tìm các đường tăng như Ford-Fulkerson hay Dinic, Push-Relabel duy trì một nhãn (label) cho mỗi đỉnh và đẩy luồng qua các cạnh theo cách tăng dần các nhãn này. Các bước chính bao gồm:
Khởi tạo: Khởi tạo tất cả các nhãn bằng 0 và thiết lập luồng sơ bộ từ nguồn đến các đỉnh kề.
Đẩy luồng (Push): Đẩy luồng từ đỉnh này sang đỉnh khác nếu đỉnh nguồn có nhiều luồng hơn khả năng chứa của đỉnh đích và các nhãn thoả mãn điều kiện.
Relabel: Tăng nhãn của một đỉnh nếu không thể đẩy thêm luồng qua các cạnh kề.
Lặp lại: Tiếp tục đẩy và relabel cho đến khi không thể đẩy thêm luồng từ nguồn đến đích.
Mỗi giải thuật có ưu và nhược điểm riêng, và việc chọn giải thuật phụ thuộc vào đặc điểm của mạng lưới và yêu cầu cụ thể của bài toán.
Nếu bạn cần thêm chi tiết về một trong các giải thuật này hoặc muốn một ví dụ cụ thể, hãy cho tôi biết!
code python c++
ChatGPT
Dưới đây là ví dụ về cách triển khai giải thuật Ford-Fulkerson để tìm luồng cực đại từ một nguồn đến một đích trong đồ thị bằng Python và C++.
Python Code:
python
Sao chép mã
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = defaultdict(list)
self.capacity = {}
def add_edge(self, u, v, w):
self.graph[u].append(v)
self.graph[v].append(u)
self.capacity[(u, v)] = w
self.capacity[(v, u)] = 0
def bfs(self, s, t, parent):
visited = [False] * self.V
queue = []
queue.append(s)
visited[s] = True
while queue:
u = queue.pop(0)
for v in self.graph[u]:
if visited[v] == False and self.capacity[(u, v)] > 0:
queue.append(v)
visited[v] = True
parent[v] = u
if v == t:
return True
return False
def ford_fulkerson(self, source, sink):
parent = [-1] * self.V
max_flow = 0
while self.bfs(source, sink, parent):
path_flow = float('Inf')
s = sink
while s != source:
path_flow = min(path_flow, self.capacity[(parent[s], s)])
s = parent[s]
v = sink
while v != source:
u = parent[v]
self.capacity[(u, v)] -= path_flow
self.capacity[(v, u)] += path_flow
v = parent[v]
max_flow += path_flow
return max_flow
# Driver code
g = Graph(6)
g.add_edge(0, 1, 16)
g.add_edge(0, 2, 13)
g.add_edge(1, 2, 10)
g.add_edge(1, 3, 12)
g.add_edge(2, 1, 4)
g.add_edge(2, 4, 14)
g.add_edge(3, 2, 9)
g.add_edge(3, 5, 20)
g.add_edge(4, 3, 7)
g.add_edge(4, 5, 4)
source = 0
sink = 5
print("The maximum possible flow is %d " % g.ford_fulkerson(source, sink))
C++ Code:
cpp
Sao chép mã
#include <iostream>
#include <limits.h>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
#define V 6 // Number of vertices in graph
bool bfs(int rGraph[V][V], int s, int t, int parent[]) {
bool visited[V];
memset(visited, 0, sizeof(visited));
queue<int> q;
q.push(s);
visited[s] = true;
parent[s] = -1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 0; v < V; v++) {
if (visited[v] == false && rGraph[u][v] > 0) {
if (v == t) {
parent[v] = u;
return true;
}
q.push(v);
parent[v] = u;
visited[v] = true;
}
}
}
return false;
}
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;
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;
}
max_flow += path_flow;
}
return max_flow;
}
int main() {
int graph[V][V] = {
{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}
};
cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5);
return 0;
}