Wikiszótár

Edmonds-Karp-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈɛdmont͡ʃkɒrpɒlɡoritmuʃ]

Főnév

Edmonds-Karp-algoritmus

  1. (matematika)

Edmonds-Karp-algoritmus

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.


Elmélet

  1. Hálózat fogalma:
    • Egy irányított gráf ((G = (V, E))) csúcsokból ((V)) és élekből ((E)) áll.
    • Minden élhez tartozik egy kapacitás ((c(u, v))).
    • Van egy forrás ((s)) és egy nyelő ((t)) csúcs.
  2. Cél:
    • Maximális áramlást találni a forrásból a nyelőbe úgy, hogy az áramlás ne lépje túl az élek kapacitását, és teljesüljön az áramlási megmaradás törvénye minden csúcson belül.
  3. Algoritmus működése:
    • Kezdjünk nulla áramlással.
    • Ismételjük, amíg találunk augmentáló utat:
      • Keressük meg az (s t) útvonalat BFS-sel az aktuális maradék gráfban.
      • Határozzuk meg a lehetséges maximális áramlást az úton ((bottleneck)).
      • Frissítsük az áramlást és a maradék gráfot.
    • Az áramlás maximális, ha nincs több augmentáló út.
  4. Maradék gráf:
    • A maradék gráf tartalmazza a kapacitásokat az aktuális áramlás figyelembevételével: [ c_{}(u, v) = c(u, v) - f(u, v) ]


Időkomplexitás

  • Komplexitás: (O(V E^2))
    • (O(E)) egy BFS költsége.
    • (O(V E)) a lehetséges augmentáló utak száma.


Pszeudokód

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

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 edmonds_karp(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:", edmonds_karp(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 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[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: " << edmonds_karp(capacity, source, sink) << endl;

    return 0;
}

Kimenet: 

Maximális áramlás: 23

Összegzés

Előnyök:

  1. Garantált konvergencia: A legrosszabb esetben is működik.
  2. Egyszerű implementáció: Könnyen követhető és megérthető.

Hátrányok:

  1. Teljesítmény: Nagyon sűrű gráfok esetén az (O(V E^2)) időkomplexitás lassú lehet.

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.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Edmonds-Karp-algoritmus&oldid=3479510”