Mastering Algorithms for Problem Solving in Java/

...

/

Relax All the Edges: Bellman-Ford

Relax All the Edges: Bellman-Ford

Get to know the Bellman-Ford algorithm and its applications in solving the shortest paths problem.

We'll cover the following...

Understanding the Bellman-Ford algorithm

The simplest implementation of Ford’s generic shortest-path algorithm was first sketched by Alfonso Shimbel in 1954, described in more detail by Edward Moore in 1957, and independently rediscovered by Max Woodbury and George Dantzig in 1957, by Richard Bellman in 1958, and by George Minty in 1958. (Neither Woodbury and Dantzig nor Minty published their algorithms.) In full compliance with Stigler’s Law, the algorithm is almost universally known as Bellman-Ford, because Bellman explicitly used Ford’s 1956 formulation of relaxing edges, although some authors refer to Bellman-Kalaba and a few early sources refer to Bellman-Shimbel.

The figure below shows a complete run of Dijkstra’s algorithm on a graph with negative edges. At each iteration, bold edges indicate predecessors; shaded vertices are in the priority queue; and the bold vertex is the next to be scanned.

The Shimbel / Moore / Woodbury-Dantzig / Bellman-Ford / Kalaba / Minty / Brosh algorithm can be summarized in one line:

BellmanBellman-Ford:Ford: Relax all the tense edges, then recurse.

Algorithm

BellmanFord(s)‾InitSSSP(s)while there is at least one tense edgefor every edge u→vif u→v is tenseRelax(u→v)\underline{BellmanFord(s)} \\ \hspace{0.4cm} InitSSSP(s) \\ \hspace{0.4cm} while\space there\space is\space at\space least\space one\space tense\space edge \\ \hspace{1cm} for\space every\space edge\space u\rightarrow v \\ \hspace{1.7cm} if\space u\rightarrow v\space is\space tense \\ \hspace{2.3cm} Relax(u\rightarrow v)

Implementation

Press + to interact
import java.util.ArrayList;
import java.util.Arrays;
@SuppressWarnings("unchecked")
public class BellmanFord {
    private static final int MAX_V = 1000;
private static ArrayList<Edge>[] adj = new ArrayList[MAX_V];
private static int[] dist = new int[MAX_V];
private static boolean[] tense = new boolean[MAX_V];
// Custom Pair class
private static class Edge {
    int to;
    int weight;
    public Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}
private static void InitSSSP(int s) {
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[s] = 0;
    tense[s] = true;
}
private static boolean HasTenseEdge() {
    for (int u = 0; u < MAX_V; u++) {
        if (tense[u]) {
            return true;
        }
    }
    return false;
}
private static void Relax(int u, int v, int weight) {
    if (dist[u] != Integer.MAX_VALUE && dist[v] > dist[u] + weight) {
        dist[v] = dist[u] + weight;
        tense[v] = true;
    }
}
private static void BellmanFord(int s) {
    InitSSSP(s);
    while (HasTenseEdge()) {
        for (int u = 0; u < MAX_V; u++) {
            for (Edge edge : adj[u]) {
                int v = edge.to;
                int weight = edge.weight;
                if (tense[u] && tense[v]) {
                    Relax(u, v, weight);
                }
            }
            tense[u] = false;
        }
    }
}
public static void main(String[] args) {
    for (int i = 0; i < MAX_V; i++) {
        adj[i] = new ArrayList<>();
    }
    adj[0].add(new Edge(1, 5));
    adj[1].add(new Edge(2, 2));
    adj[2].add(new Edge(3, 3));
    adj[3].add(new Edge(4, -4));
    adj[4].add(new Edge(1, 1));
    BellmanFord(0);
    for (int i = 0; i < MAX_V; i++) {
        System.out.println("Shortest distance from vertex 0 to " + i + " is " + dist[i]);
        }
    }
}

Explanation

  • Lines 20–24: This function initializes the single-source shortest path algorithm by setting all distances to the maximum value except for the source vertex which is set to zero, and marking it as tense.
  • Lines 42–56: This is the implementation of the Bellman-Ford algorithm explained above.
  • Lines 62–67: These lines of code add edges in the example graph.

The following lemma is the key to proving both the correctness and efficiency of Bellman-Ford. For every vertex vv and non-negative integer ii, let dist≤i(v)dist≤i(v) denote the length of the shortest walk in GG from ss to vv consisting of at most ii edges. In particular, dist≤0(s)=0dist≤_0(s) = 0 and dist≤0(v)=∞dist≤_0(v) = ∞ for all v≠sv \neq s.

Lemma: For every vertex vv and non-negative integer ii, after ii iterations of the main loop of Bellman-Ford, we have dist(v)≤dist≤i(v)dist(v) ≤ dist≤_i(v).

Proof: The proof proceeds by induction on ii. The base case i=0i = 0 is trivial, so assume i>0i > 0. Fix a vertex vv, and let WW be the shortest walk from ss to vv consisting of at most ii edges (breaking ties arbitrarily). By definition, WW has length dist≤i(v)dist≤_i(v). There are two cases to consider:

  • Suppose WW has no edges. Then W must be the trivial walk from ss to ss, so v=sv = s and dist≤i(s)=0dist≤_i(s) = 0. We set dist(s)←0dist(s) ← 0 in InitSSSPInitSSSP, and dist(s)dist(s) can never increase, so we always have
...