Edmonds-Karp algorithm

Edmonds-Karp algorithm (tsz. Edmonds-Karp algorithms)

1. (informatika) Edmonds-Karp-algoritmus

Az Edmonds–Karp algoritmus a Ford–Fulkerson-módszer egy konkrét megvalósítása maximális áramlás (max-flow) problémára irányított, kapacitással ellátott hálózatokban. A kulcslépés: minden augmentáló utat nem mélységi, hanem szélességi kereséssel (BFS) találunk, így garantáltan az élek szerinti legrövidebb augmentáló utakat használjuk.

2. Algoritmus vázlata

1. Inicializálás

   • Minden él ${\textstyle (u,v)}$ kezdetben nullás áramlást kap: ${\textstyle f(u,v)=0}$.

   • A maradékgráf ${\textstyle G_{f}}$ kapacitásai:

     $${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v),\quad c_{f}(v,u)=f(u,v).}$$

2. Augmentáló út keresése

   • Minden iterációban BFS-sel keressük meg az ${\textstyle s\to t}$ útvonalat a maradékgráfban, csak olyan éleken haladva, ahol ${\textstyle c_{f}>0}$.
   • A BFS biztosítja, hogy az út él­száma minimális legyen.

3. Bővítés (augmentation)

   • Ha találtunk egy útvonalat ${\textstyle P}$, annak bottleneck kapacitása: ${\textstyle \Delta =\min _{(u,v)\in P}c_{f}(u,v)}$.

   • Minden $ (u,v)P$ élre növeljük az áramlást:

     $${\displaystyle f(u,v)\;+\!=\;\Delta ,\quad f(v,u)\;-\!=\;\Delta .}$$

4. Ismétlés

   • Amíg van ${\textstyle s\to t}$ út a maradékgráfban, ismételjük a BFS-t és a bővítést.
   • Ha BFS nem talál utat, akkor az aktuális ${\textstyle f}$ maximális.

3. Pseudokód

EdmondsKarp(G, c, s, t):
    // G = (V,E), c(u,v) kapacitás, s forrás, t nyelő
    f(u,v) = 0 minden (u,v) ∈ E
    max_flow = 0

    while van út P: s → t a maradékgráfban (BFS-en keresztül):
        // Bottleneck
        Δ = min{ c(u,v) - f(u,v) | (u,v) ∈ P }
        // Áramlás frissítése
        for minden (u,v) ∈ P:
            f(u,v) += Δ
            f(v,u) -= Δ
        max_flow += Δ

    return max_flow, f

4. Időkomplexitás

• Minden iterációban egy BFS fut, ami ${\textstyle O(E+V)}$.

• Legrosszabb esetben az augmentációk száma ${\textstyle O(VE)}$ (mivel minden bővítés legalább egy él maradékkapacitását csökkenti, és összesen legfeljebb ${\textstyle E}$ különböző bottleneck-értékű változás lehet, mindegyiken át legfeljebb ${\textstyle V}$ bővítés).

• Így az Edmonds–Karp időkomplexitása:

  $${\displaystyle O(VE)\times O(E+V)=O(VE^{2}).}$$

5. Példa lépésről lépésre Legyen a hálózat:

 s → u → v → t
 |    ↘     ↑
 ↓     w → x

Kapacitások (rövid jelöléssel):

$${\displaystyle c(s,u)=10,\;c(s,w)=5,\;c(u,v)=4,\;c(u,w)=2,\;c(w,x)=3,\;c(x,v)=6,\;c(v,t)=8.}$$

1. 1. iteráció (BFS): út ${\textstyle s,u,v,t}$, bottleneck = ${\textstyle \min(10,4,8)=4}$. → növeljük ezen az úton ${\textstyle f=4}$.
2. 2. iteráció: maradékgráfban újabb BFS: ${\textstyle s,w,x,v,t}$, bottleneck = ${\textstyle \min(5,3,6,4)=3}$. → augmentálunk 3-mal.
3. 3. iteráció: például út ${\textstyle s,u,w,x,v,t}$ vagy más, amíg nincs további Értelmezés sikertelen (formai hiba): {\textstyle s→t} út (ha az összes út élei lekorlátozódnak).
4. Végül ${\textstyle \max \_flow=4+3+\dots }$.

6. Python-implementáció

from collections import deque, defaultdict

def edmonds_karp(capacity, s, t):
    flow = defaultdict(lambda: defaultdict(int))
    max_flow = 0

    def bfs():
        parent = {s: None}
        q = deque()
        while q:
            u = q.popleft()
            for v in capacity:
                if v not in parent and capacity - flow > 0:
                    parent = u
                    if v == t:
                        return parent
                    q.append(v)
        return None

    while True:
        parent = bfs()
        if not parent:
            break
        # Bottleneck-érték számítása
        v = t
        delta = float('inf')
        while v != s:
            u = parent
            delta = min(delta, capacity - flow)
            v = u
        # Áramlás augmentálása
        v = t
        while v != s:
            u = parent
            flow += delta
            flow -= delta
            v = u
        max_flow += delta

    return max_flow, flow

# Példa hálózat definíciója
capacity = defaultdict(dict)
capacity = {'u':10, 'w':5}
capacity = {'v':4, 'w':2}
capacity = {'x':3}
capacity = {'v':6}
capacity = {'t':8}

max_flow, flow = edmonds_karp(capacity, 's', 't')
print("Maximális áramlás:", max_flow)

7. Alkalmazások

• Hálózati adatátvitel: csomagok maximális száma sávszélességkorlátok mellett.
• Párosítás kétoldalú gráfokon (maximum bipartit matching).
• Képfeldolgozás: min-cut/max-flow alapú képszegmentálás.
• Logisztikai tervezés: áruk hegymenetének optimalizálása.

8. Összefoglalás Az Edmonds–Karp algoritmus egyszerűen implementálható változata a Ford–Fulkerson-nak, BFS-sel biztosítva az augmentáló utak él­szám szerinti minimalitását. Noha elméleti időkomplexitása ${\textstyle O(VE^{2})}$, gyakorlati problémákban gyakran megfelelő, és alapul szolgál fejlettebb max-flow eljárásoknak.

• Edmonds-Karp algorithm - Szótár.net (en-hu)
• Edmonds-Karp algorithm - Sztaki (en-hu)
• Edmonds-Karp algorithm - Merriam–Webster
• Edmonds-Karp algorithm - Cambridge
• Edmonds-Karp algorithm - WordNet
• Edmonds-Karp algorithm - Яндекс (en-ru)
• Edmonds-Karp algorithm - Google (en-hu)
• Edmonds-Karp algorithm - Wikidata
• Edmonds-Karp algorithm - Wikipédia (angol)