Bellman‐Ford Algorithm - rFronteddu/general_wiki GitHub Wiki

This algorithm solves the single-source shortest-path problem (s-ss-p) in the general case (edge weights may be negative).

Given a weighted, directed graph G = (V,E) which source s and weight function w:E->R, this algorithm returns whether or not there is a negative-weight cycle that is reachable from the source.

If there is, no solution exists. Otherwise it produces the s-p and their weights. The algorithm relaxes edges, progressively decreasing an estimate v.d on the weight of a s-p from the source s to each vertex v until it achieves the actual s-p weight.

// O(V*E)
BelmanFord(G,w,s)
    // O (V)
    initializeSingleSource (G,s)
    
    // O(V*E)
    for i = 1 to |G.V| - 1
        for (u,v) in G.E
            relax (u,v,w)
     
    // check for negative cycles
    // O (E)
    for (u,v) in G.E
        if v.d > u.d + w(u,v)
            return false
    return true

// O(V)
initializeSingleSource (G,s)
    for v in G.V
        v.d = max
        v.p = nil
    s.d = 0

relax (u,v,w)
    if v.d > u.d + w (u,v)
        v.d = u.d + w (u,v)
        v.p = u

• Bellman Ford Java