Bellman-Ford-Algorithmus

Dieser Algorithmus ist ein Beispiel für dynamische Programmierung.

Sei B_k[i]:= Länge eines kürzesten Pfades von s zu Knoten i, der höchstens k Kanten enthält.
Gesucht ist B_n-1[i]; für $i=1,\cdots, n$, Menge der Knoten $V=\{1,\cdots,n\}$

Initialisierung:

$$B_1[i]:= \left\{ \begin{array} {ll} \text{d}(s,i) &, \text... ...falls } i=s;\\ +\infty & , \text{sonst}\\ \end{array} \right.$$

Iteration:

		  for k=2 to n-1 do
		 		 for i=1 to n do
		 		 		 $B_k[i]:=
\left\{ 
\begin{array}
{ll}
 0 & , \text{falls } i=s;\\ \min_{j\in N(i...
 ...B_{k-1}[i], B_{k-1}[j]+\text{d}(j,i) \} &, \text{sonst}\\ \end{array} 
\right.$		 		 od
		 od

Korrekheit: klar (Beweis durch vollständige Induktion)

Zeitbedarf: Wenn die innere Laufschleife durch eine Schleife über alle Kanten ersetzt wird: