Shortest Paths: Bellman-Ford Algorithm
BellmanFord(G=(V,E), s in V)
W[n][n]: new array
set W[0][s]=0, set W[0][j]=infty for j not s
for i = 1 to n
for each j in V
set best = W[i-1][j]
for each u with (u,j) in E
newPath = c(u,j) + W[i-1][u]
if newPath < best
set best = newPath
W[i][j] = best
return W[n-1]
Run the Bellman-Ford algorithm on the above graph, filling in the following table:
0
s
q
t
x
y
z
1
2
3
4
5