A Ford-Fulkerson-algoritmus egy hatékony módszer a hálózati maximális áramlás probléma megoldására. Az algoritmus a maradékgráf koncepcióján alapul, és iteratív módon keresi meg a forrástól a nyelőig vezető augmentáló utakat, amíg nem találhatók további utak.
Egy irányított gráfban ((G = (V, E))) a cél a forrástól ((s)) a nyelőig ((t)) történő áramlás maximalizálása az élek kapacitáskorlátainak figyelembevételével.
FordFulkerson(G, s, t):
inicializálj minden élhez 0 áramlást
amíg létezik augmentáló út s-től t-ig:
bottleneck = a legkisebb kapacitás az úton
növeld az áramlást az augmentáló út mentén bottleneck-kel
frissítsd a maradékgráfot
térj vissza az összes áramlás összegével
from collections import deque
def bfs(residual_graph, source, sink, parent):
visited = set()
queue = deque()
visited.add(source)
while queue:
u = queue.popleft()
for v, capacity in enumerate(residual_graph):
if v not in visited and capacity > 0:
parent = u
if v == sink:
return True
visited.add(v)
queue.append(v)
return False
def ford_fulkerson(capacity, source, sink):
n = len(capacity)
residual_graph = for row in capacity]
parent = * n
max_flow = 0
while bfs(residual_graph, source, sink, parent):
# Keressük a bottleneck kapacitást
path_flow = float('Inf')
v = sink
while v != source:
u = parent
path_flow = min(path_flow, residual_graph)
v = u
# Frissítsük az áramlást és a maradék gráfot
v = sink
while v != source:
u = parent
residual_graph -= path_flow
residual_graph += path_flow
v = u
max_flow += path_flow
return max_flow
# Példa gráf (kapacitás mátrix formátumban)
capacity = [
,
,
,
,
,
]
source, sink = 0, 5
print("Maximális áramlás:", ford_fulkerson(capacity, source, sink))
Kimenet:
Maximális áramlás: 23
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <cstring>
using namespace std;
bool bfs(const vector<vector<int>>& residual_graph, int source, int sink, vector<int>& parent) {
int n = residual_graph.size();
vector<bool> visited(n, false);
queue<int> q;
q.push(source);
visited = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 0; v < n; ++v) {
if (!visited && residual_graph > 0) {
parent = u;
if (v == sink) return true;
visited = true;
q.push(v);
}
}
}
return false;
}
int ford_fulkerson(const vector<vector<int>>& capacity, int source, int sink) {
int n = capacity.size();
vector<vector<int>> residual_graph = capacity;
vector<int> parent(n, -1);
int max_flow = 0;
while (bfs(residual_graph, source, sink, parent)) {
// Keressük a bottleneck kapacitást
int path_flow = INT_MAX;
for (int v = sink; v != source; v = parent) {
int u = parent;
path_flow = min(path_flow, residual_graph);
}
// Frissítsük az áramlást és a maradék gráfot
for (int v = sink; v != source; v = parent) {
int u = parent;
residual_graph -= path_flow;
residual_graph += path_flow;
}
max_flow += path_flow;
}
return max_flow;
}
int main() {
vector<vector<int>> capacity = {
{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 source = 0, sink = 5;
cout << "Maximális áramlás: " << ford_fulkerson(capacity, source, sink) << endl;
return 0;
}
Kimenet:
Maximális áramlás: 23
A Ford-Fulkerson-algoritmus az áramlásoptimalizálás alapvető eszköze, amelyet számos gyakorlati alkalmazásban, például hálózattervezésben és logisztikában használnak.