// Shortest paths with negative edges
Shortest-Path(G, t) {
foreach node v ∈ V
M[0, v] <- infinity
M[0, t] <- 0
for i = 1 to n-1
foreach node v ∈ V
M[i ,v] <- M[i-1, v]
foreach edge(v,w) ∈ E
M[i,v] <- min{ M[i,v], M[i-1, w] Cvw}
}
// big theta(mn) time big theta(n square) space
// Finding the shortest paths
// Maintain a "successor" for each table entry
Bellman-Ford 算法
代码语言：javascript复制
//Bellman-Ford algorithm
d[s] <- 0
for each v ∈ V-{s}
do d[v] <- infinity
for i <- 1 to |V| - 1
do for each edge(u, v) ∈ E
do if d[v] > d[u] w(u,v)
then d[v] <- d[u] w(u,v) // relaxation step
for each edge(u,v) ∈ E
do if d[v] > d[u] w(u,v)
then report that a negative-weight cycle exists
At the end, d[v] = delta(s, v), if no negative-weight cycles
Time = O(VE)
