Bellman-Ford algorithm

Bellman-Ford algorithm (tsz. Bellman-Ford algorithms)

1. (informatika) Bellman-Ford-algoritmus

A Bellman–Ford algoritmus egy gráfbejáró eljárás, amely egy adott kezdőcsúcstól (forrástól) minden más csúcsig a legrövidebb út hosszát számítja ki súlyozott, irányított gráfokban, akár negatív él­súlyokkal is. Emellett képes kimutatni, ha negatív súlyú kör (cycle) létezik, amelyre a legrövidebb út nem definiált (végtelenül csökkenthető).

2. Az algoritmus ötlete

1. Inicializálás

   • Minden csúcs ${\textstyle v}$ távolságát ${\textstyle \mathrm {dist} }$-vel jelöljük, kezdetben ${\textstyle \infty }$, kivéve a forrást, ahol ${\textstyle \mathrm {dist} =0}$.
   • Egy parent mutató a visszakövethető úthoz (opcionális).

2. Relaxeálás (élcsökkentés) – Minden élen ${\textstyle (u,v)}$ a súlyával ${\textstyle w(u,v)}$ megpróbáljuk csökkenteni a rá vonatkozó távolságbecslést:

   $${\displaystyle {\text{ha }}\mathrm {dist} +w(u,v)<\mathrm {dist} {\text{, akkor }}\mathrm {dist} =\mathrm {dist} +w(u,v),\;\mathrm {parent} =u.}$$

   – Ez a művelet biztosítja, hogy iterációról iterációra egyre pontosabb becsléseink legyenek.

3. Iterációk száma – Egy gráf legrövidebb útjai legfeljebb ${\textstyle |V|-1}$ élből állnak, ahol ${\textstyle |V|}$ a csúcsok száma. – Így ${\textstyle |V|-1}$ teljes “relaxeálási kört” futtatunk végig az összes élen, ami garantálja, hogy minden csúcs távolsága konvergáljon a valódi legkisebb értékre.

4. Negatív kör detektálás – Végül még egyetlen plusz relaxációs körön menünk át az éleken. – Ha ilyenkor bármely él tovább tud csökkenteni egy csúcs távolságát, akkor negatív kör létezik, mert ekkor a legrövidebb út hosszát végtelenül csökkenteni lehet.

3. Pseudokód

BellmanFord(G, w, s):
    // G = (V, E) irányított gráf, w: E→ℝ súlyfüggvény, s: forráscsúcs
    for minden v ∈ V:
        dist = ∞
        parent = NIL
    dist = 0

    // |V|-1 relaxációs kör
    for i = 1 to |V|-1:
        for minden (u, v) ∈ E:
            if dist + w(u, v) < dist:
                dist = dist + w(u, v)
                parent = u

    // Negatív kör ellenőrzés
    for minden (u, v) ∈ E:
        if dist + w(u, v) < dist:
            return "Negatív kör található"

    return dist, parent

4. Idő- és helykomplexitás

• Időkomplexitás:
  • Az ${\textstyle |V|-1}$ iteráció mindegyikében az összes ${\textstyle |E|}$ élen végigmegyünk ⇒ ${\textstyle O(|V|\cdot |E|)}$.
  • A negatív kör ellenőrzése további ${\textstyle O(|E|)}$, így összesen ${\textstyle O(|V|\cdot |E|)}$.
• Helykomplexitás:
  • Tárolunk egy dist és egy parent tömböt ⇒ ${\textstyle O(|V|)}$.

5. Példa lépésről lépésre Legyen az alábbi gráf, élsúlyokkal:

      (5)
  A ——→ B
  |      \
(2)|       \(2)
  ↓        C
  D ←—— E
     (−4)

Élek:

• A→B (5), A→D (2), B→C (2), E→D (−4), C→E (3)

Forrás: ${\textstyle s=A}$.

1. Kezdeti állapot

   dist=0, dist=∞, dist=∞, dist=∞, dist=∞

2. 1. relaxációs kör

   • A→B: 0+5 < ∞ ⇒ dist=5
   • A→D: 0+2 < ∞ ⇒ dist=2
   • B→C: 5+2 < ∞ ⇒ dist=7
   • C→E: 7+3 < ∞ ⇒ dist=10
   • E→D: 10+(−4) < 2 ⇒ dist=6 (nem frissítjük, mert 6>2 marad)

3. 2. kör

   • A→B: nem változik (0+5=5)
   • A→D: nem változik
   • B→C: nem változik
   • C→E: 7+3=10 (nem változik)
   • E→D: 10−4=6 > 2 (nem változik)

4. 3. kör (|V|=5 ⇒ 4 relaxációs körig megyünk, de láthatóan gyorsan konvergált)

   – További körökben nem történik változás, így a konvergencia már korábban bekövetkezett.

5. Negatív kör ellenőrzés – Semelyik él esetében nem csökkenthető tovább az érték ⇒ nincs negatív kör.

Végül:

dist = {A:0, B:5, C:7, D:2, E:10}
parent = {A:NIL, B:A, C:B, D:A, E:C}

6. Python-példa

def bellman_ford(graph, source):
    """
    graph: lista az élekről, minden él (u, v, w)
    source: forráscsúcs
    Visszatér: (dist, parent) vagy hibajelzés negatív kör esetén
    """
    # Csúcsok kigyűjtése
    vertices = set()
    for u, v, w in graph:
        vertices.add(u); vertices.add(v)
    dist = {v: float('inf') for v in vertices}
    parent = {v: None for v in vertices}
    dist = 0

    # |V|-1 relaxáció
    for _ in range(len(vertices) - 1):
        updated = False
        for u, v, w in graph:
            if dist + w < dist:
                dist = dist + w
                parent = u
                updated = True
        if not updated:
            break  # ha nem változott semmi, már konvergált

    # Negatív kör ellenőrzés
    for u, v, w in graph:
        if dist + w < dist:
            raise ValueError("Negatív súlyú kör található")

    return dist, parent

# Példa használat
edges = [
    ('A','B',5), ('A','D',2), ('B','C',2),
    ('C','E',3), ('E','D',-4)
]
distances, parents = bellman_ford(edges, 'A')
print("Távolságok:", distances)
print("Szülők:", parents)

7. Alkalmazások és összehasonlítás

• Negatív él­súlyok kezelése: Dijkstra nem alkalmas negatív súlyokra, Bellman–Ford viszont igen.
• Negatív kör detektálás: ha a probléma modellezése során negatív ciklus fordul elő (pl. arbitrázs a pénzügyi hálózatokban), azt ez az algoritmus azonosítani tudja.
• Hálózati útvonalválasztás: például a RIP (Routing Information Protocol) hálózati útválasztási algoritmus alapelve hasonló relaxációs folyamatot alkalmaz.

8. Összefoglalás A Bellman–Ford algoritmus robusztus eszköz súlyozott gráfok legrövidebb útjainak kiszámítására, különösen negatív él­súlyok esetén, és egyszerű módon detektálja a negatív köröket. Bár időkomplexitása ${\textstyle O(|V|\cdot |E|)}$ miatt nagy gráfokban lassabb lehet, előnye a szélesebb alkalmazhatóság és a negatív kör érzékelése.

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