Bellman-Ford solves the single source shortest path problem via a brute force approach.
It can also detect negative weight cycles
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
for initialisation + for relaxation + for negative edge check