Bellman-Ford Algorithm

Bellman-Ford solves the single source shortest path problem via a brute force approach.

It can also detect Negative Weight Cycle

Pseudocode §

Algorithm Bellman-Ford(G, source):n

	For vertex v in G do: #O(|V|)
		v.dist ← ∞ #Storage of node attributes for memoization 
		v.parent ← None
	End do
	source.dist ← 0
	For i from 1 to |V| - 1 do: #O(|V|)
		For edge (u-v-w) in G do: #O(|E|)
			If u.dist + w < v.dist then:
				v.dist ← u.dist + w
				v.parent ← u
			End if
		End do
	End do

	//Detect negative edge cycles here
	For edge (u-v-w) in G do: #O(|E|)
		If (u.dist + w < v.dist):
			Return "Negative Weight Cycle Found"

End Algorithm

Complexity §

Time Complexity:

$O(|V|)$ for initialisation + $O(|V|\ast |E|)$ for relaxation + $O(|E)$ for negative edge check

$O(|V|\ast |E|)$

Implementation §