Bellman-Ford Algorithm (C++)

Table of contents

1. Things to Remember
2. Adjacency List
3. Initialization
   1. Distance and Predecessor Vectors
   2. Source Initialization
4. The Loop (Naive Version)
5. Detecting Negative Cycles
6. Adjacency List in DP Version
7. Initialization in DP Version

---

Things to Remember

• We have a naive version and a dynamic programming version.
• Can handle negative edge weights.
• Detects negative cycles.
• We need to build an adjacency list to represent the graph.
• We do not use a priority queue.

---

Adjacency List

The adjacency list adj needs to be built with given inputs:

using Dist = int;
using Vertex = int;
using EdgeTo = pair<Dist, Vertex>;  // Do not confuse this with the PqElem later

vector<vector<EdgeTo>> adj(n + 1);  // If vertices are 1-indexed
// Build the adjacency list with loop
  adj[u].push_back({w, v});  // Edge from u to v with weight w

---

Initialization

Distance and Predecessor Vectors

We will keep track of the current shortest distance and current predecessor of each vertex.

vector<AccDist> cur_dist(n + 1, INT_MAX);
vector<Vertex> pred(n + 1, -1);

Source Initialization

Let’s say we are starting from vertex s.

First, we know the shortest distance to s from s is 0.

cur_dist[s] = 0;

Obviously, predecessor of the source vertex remains -1.

---

The Loop (Naive Version)

for (int round = 1; round < n; ++round) {
  for (int u = 1; u <= n; ++u) {
    for (const EdgeTo& e : adj[u]) {
      int w = e.first;
      int v = e.second;
      if (cur_dist[u] != INT_MAX && cur_dist[v] > cur_dist[u] + w) {
        cur_dist[v] = cur_dist[u] + w;
        pred[v] = u;
      }
    }
  }
}

---

Detecting Negative Cycles

To detect negative cycles, we need to run the loop one more time.

If we can relax any edge, then there is a negative cycle.

for (int u = 1; u <= n; ++u) {
  for (const EdgeTo& e : adj[u]) {
    int w = e.first;
    int v = e.second;
    if (cur_dist[u] != INT_MAX && cur_dist[v] > cur_dist[u] + w) {
      cout << "Negative cycle detected!" << endl;
      return;
    }
  }
}

---

Adjacency List in DP Version

In the bottom-up DP version, we need to build the adjacency list so that each index corresponds to a vector of incoming edges.

vector<vector<EdgeFrom>> adj(n + 1);
...
  adj[v].push_back({w, u});  // For each edge (u, v) in the input

---

Initialization in DP Version

We need a memoization table W to store the shortest distances. The rows correspond to the the maximum number of edges a path can have, and the columns correspond to the destination vertex.

vector<vector<int>> W(n);
  for (int m = 0; m < n; ++m) {
    W[m] = vector<int>(n + 1, INT_MAX);
    for (int i = 1; i <= n; ++i) {
      if (i == k) W[m][i] = 0;
    }
  }

All the entries are initialized to INT_MAX except for the source vertex column, which can be reached in 0 distance.