Az Edmonds-Karp-algoritmus a Ford-Fulkerson-algoritmus specializált változata, amely hatékonyan számítja ki egy hálózat maximális áramlását. Az algoritmus a Ford-Fulkerson módszert alkalmazza úgy, hogy a legkisebb számú élt tartalmazó utakat (azaz szélességi keresést - BFS-t) használja az augmentáló utak megtalálásához.
EdmondsKarp(G, s, t):
inicializálj minden élhez tartozó áramlást nullára
amíg van augmentáló út s-től t-ig BFS-sel:
határozd meg az út kapacitását (bottleneck)
frissítsd az áramlást az úton
frissítsd a maradék gráfot
térj vissza a maximális áramlás értéké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 edmonds_karp(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:", edmonds_karp(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 edmonds_karp(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: " << edmonds_karp(capacity, source, sink) << endl;
return 0;
}
Kimenet:
Maximális áramlás: 23
Az Edmonds-Karp-algoritmus széles körben használt az áramlási problémák megoldására, és egyszerűsége miatt kiváló választás tanulmányozásra vagy alapvető implementációra.