Ford-Fulkerson-algoritmus
Kiejtés
- IPA: [ ˈfortfulkɛrʃonɒlɡoritmuʃ]
Főnév
Ford-Fulkerson-algoritmus
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.
Probléma leírása
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.
Definíciók:
- Kapacitás ((c(u, v))): Az él maximális áramlási kapacitása (u)-ból (v)-be.
- Áramlás ((f(u, v))): Az él mentén áramló tényleges érték, amelynek: [ 0 f(u, v) c(u, v) ] és teljesülnie kell az áramlási megmaradás törvényének: [ {v V} f(u, v) = {v V} f(v, u) ]
- Maradékgráf ((G_f)): Az aktuális áramlás figyelembevételével a további áramlások lehetőségeit mutatja meg: [ c_f(u, v) = c(u, v) - f(u, v) ]
Algoritmus lépései
- Indítás:
- Kezdjük nullával az összes él mentén ((f(u, v) = 0)).
- Hozzunk létre egy maradékgráfot, amely kezdetben az eredeti gráffal megegyezik.
- Augmentáló út keresése:
- Keressünk egy utat a forrástól ((s)) a nyelőig ((t)) a maradékgráfban (például BFS-sel vagy DFS-sel).
- Áramlás növelése:
- Határozzuk meg az augmentáló út mentén elérhető legkisebb kapacitást ((bottleneck)).
- Növeljük az áramlást az augmentáló út mentén ezzel az értékkel.
- Maradékgráf frissítése:
- Frissítsük a kapacitásokat és az áramlásokat: [ c_f(u, v) = c_f(u, v) - bottleneck ] [ c_f(v, u) = c_f(v, u) + bottleneck ]
- Ismétlés:
- Ismételjük az augmentáló utak keresését, amíg nem találunk további utat.
- Végeredmény:
- Az összes augmentáló út által hozzáadott áramlás a maximális áramlás értékét adja.
Időkomplexitás
- Az algoritmus időkomplexitása (O(E )), ahol:
- (E): élek száma.
- (): a maximális áramlás értéke.
Pszeudokód
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
Python implementáció
from collections import deque
def bfs(residual_graph, source, sink, parent):
visited = set()
queue = deque([source])
visited.add(source)
while queue:
u = queue.popleft()
for v, capacity in enumerate(residual_graph[u]):
if v not in visited and capacity > 0:
parent[v] = 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 = [row[:] for row in capacity]
parent = [-1] * 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[v]
path_flow = min(path_flow, residual_graph[u][v])
v = u
# Frissítsük az áramlást és a maradék gráfot
v = sink
while v != source:
u = parent[v]
residual_graph[u][v] -= path_flow
residual_graph[v][u] += path_flow
v = u
max_flow += path_flow
return max_flow
# Példa gráf (kapacitás mátrix formátumban)
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]
]
source, sink = 0, 5
print("Maximális áramlás:", ford_fulkerson(capacity, source, sink))
Kimenet:
Maximális áramlás: 23
C++ implementáció
#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[source] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 0; v < n; ++v) {
if (!visited[v] && residual_graph[u][v] > 0) {
parent[v] = u;
if (v == sink) return true;
visited[v] = 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[v]) {
int u = parent[v];
path_flow = min(path_flow, residual_graph[u][v]);
}
// Frissítsük az áramlást és a maradék gráfot
for (int v = sink; v != source; v = parent[v]) {
int u = parent[v];
residual_graph[u][v] -= path_flow;
residual_graph[v][u] += 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
Összegzés
Előnyök:
- Hatékony és egyszerű.
- Könnyen általánosítható különböző áramlási problémákra.
Hátrányok:
- Nagy kapacitású gráfok esetén lassú lehet (az augmentáló utak száma megnőhet).
- Ha az élek kapacitása irracionális szám, az algoritmus nem garantálja a befejezést.
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.
- Ford-Fulkerson-algoritmus - Értelmező szótár (MEK)
- Ford-Fulkerson-algoritmus - Etimológiai szótár (UMIL)
- Ford-Fulkerson-algoritmus - Szótár.net (hu-hu)
- Ford-Fulkerson-algoritmus - DeepL (hu-de)
- Ford-Fulkerson-algoritmus - Яндекс (hu-ru)
- Ford-Fulkerson-algoritmus - Google (hu-en)
- Ford-Fulkerson-algoritmus - Helyesírási szótár (MTA)
- Ford-Fulkerson-algoritmus - Wikidata
- Ford-Fulkerson-algoritmus - Wikipédia (magyar)