Modifikation von Bellman-Ford-Algorithmus

B_k[i] gibt nun die Länge eines kürzesten gerichteten s-i-Pfades an, der aus höchstens k Kanten besteht. Jeder beliebige Kantenzug, der keinen Kreis enthält, besteht aus maximal n-1 Kanten. In einem Graphen ohne negative Kreise gilt daher:

$$\forall i \in V : B_n[i] \geq B_{n-1}[i]$$

Gibt es dagegen einen (von s aus erreichbaren) negativen Kreis, so gibt es einen Knoten $i\in V$, bei dem ein Kantenzug aus n Kanten mit der Länge B_n[i] diesen Kreis häufiger durchläuft als jeder Kantenzug aus maximal n-1 Kanten der Länge B_n-1[i]. Demnach gilt:

B_n[i] < B_n-1[i]

Man kann also in den Algorithmus aus Bellman-Ford einen Test auf negative Kreise einbauen, indem man in der Rekursion auch $\forall i\in V: B_n[i]$ berechnet und direkt vor der Ausgabe den folgenden Befehl einfügt:

for i 1 to n do
		 if Bn[i] < Bn-1[i] then stop.