Algorithmus von Bellman und Ford

Einfache Sprache

Der Algorithmus von Bellman und Ford löst das Kürzester Pfad Problem. Für alle Knoten wird geschaut durch welchen angrenzenden Knoten es den kürzesten Weg gibt. Da sich das Ändern kann, vor allem weil manchmal Wege mit mehreren kurzen Kanten kürzer sind als Wege mit wenigen Kanten, muss das so oft wie es Knoten gibt wiederholt werden.

Idee Algorithmus von Bellman und Ford

Nutzt die Bellman-Gleichung aus. Es wird für jeden Knoten geschaut durch welchen Knoten man ihn ab kürzesten Erreichen kann. Das muss $|V|$ mal wiederholt werden, wegen: Voraussetzung für den Algorithmus ist, dass der Graph keine gerichteten Kreise negativer Länge besitzt. Also die minimale Zyklus-Länge $ZL\geq 0$ ist

Algorithmus

 1def bellman_ford(G, A):
 2    V, E = G
 3    n = len(V)
 4    u = {}
 5    # Initialize u[j,1] = a_{1j} for all j
 6    for j in range(n):
 7        u[(j, 1)] = A[0][j]
 8   for k in range(2, n):
 9        for j in range(n):
10            # Get all possible h values (h ≠ j)
11            candidates = [u[(h, k-1)] + A[h][j] for h in range(n) if h != j]
12            # Include the previous value u[j,k-1] in comparison
13            u[(j, k)] = min([u[(j, k-1)]] + candidates)
14    # Extract final distances
15    distances = [u[(j, n-1)] for j in range(n)]
16    return distances

Naive Laufzeit ist $\mathcal O(|V|^3)$. Durch geeignete Implementierung kann auch $\mathcal O(|V|\cdot|E|)$ erreicht werden.

Example

Gegeben sei folgender Graph: Der Algorithmus von Bellman und Ford produziert folgende Tabelle: D.h. wir erhalten $u_1 = 0, u_2 = −1, u_3 = 1, u_4 = 2 \text{ und } u_5 = 2$. (Also z.B. ist die Länge des kürzesten Weges zu $u_4$ gleich $2$)