Algorithmus von Bellmann-Ford

Algorithmus:
Der Algorithmus von Bellmann-Ford löst das SSSP-Problem mit dynamischer Programmierung. Sei $B_k[u]$ Länge eines kürzesten Pfades vom Startknoten zu $u$, der max. $k$ Knoten enthält. Gesucht ist $B_{n-1}[u]$.
Es gilt: $B_k[u] = min_{v \in N(u)} \{ B_{k-1}[u], B_{k-1}[v]+d(v,u) \}$
Dabei bezeichnet $N(u)$ die Nachbarschaft (also alle Nachbarn) von $u$.

Pseudocode:
forall $k$
forall $u$
forall $v \in N(u)$
$B_k[u] = min_{v \in N(u)} \{ B_{k-1}[u], B_{k-1}[v]+d(v,u) \}$

Komplexität:
Der Algorithmus von Bellmann-Ford löst das SSSP-Problem in Zeit $O(n \cdot m)$. Anstelle der beiden inneren Schleifen reicht eine Schleife über alle $m$ Nachbarn der Knoten.