Bellman-Ford Algorithm

BELLMAN-FORM(G, w, s)
    for i = 1 to |G.V| - 1
        for each edge (u, v) in G.E
            RELEAX(u, v, w)
    for each edge (u, v) in G.E
        if v.d > u.d + w(u, v)
            return False
    return True

$O (V^{2} + V E)$ , or $O (V E)$ when $∣ E ∣ = Ω (V)$ .