Type the BELLMAN-FORD pseudocode

Answer

BELLMAN-FORD(G, w, s): INITIALIZE-SINGLE-SOURCE(G, s) for i = 1 to |G.V| - 1: for each edge (u, v) in G.E: RELAX(u, v, w) for each edge (u, v) in G.E: if v.d > u.d + w(u, v): return FALSE # negative cycle return TRUE

The |V|−1 passes settle every simple shortest path (at most |V|−1 edges). The final pass tests for a still-relaxable edge, which can only happen when a reachable negative-weight cycle exists.