Floyd-Warshall Algorithm (C++)

Table of contents

1. Things to Remember
2. Initialization
3. The Loop

---

Things to Remember

• Floyd-Warshall algorithm is a dynamic programming algorithm.
• It finds the shortest path between all pairs of vertices.
• It can handle negative edge weights.
• It runs in $O(n^3)$ time.
• We need to build an adjacency matrix to represent the graph.

---

Initialization

From the given inputs, we need to build an $n \times n$ shortest distance matrix D, where each element $D_{ij}$ representsthe shortest distance from node $i$ to node $j$.

We also need to build an $n \times n$ predecessor matrix P, where each element $P_{ij}$ represents the immediate predecessor of node $j$ on the shortest path from node $i$.

using AccD = int;
using Node = int;
vector<vector<AccD>> D(n, vector<AccD>(n, INT_MAX));
vector<vector<Node>> P(n, vector<Node>(n, -1));

The shortest distance from a vertex to itself is always 0:

for (int i = 0; i < n; ++i) {
  D[i][i] = 0;
}

Now we initialize the matrices with single edges:

for (const auto& e : input) {
  // i, j, w
  D[i][j] = w;
  P[i][j] = i;
}

---

The Loop

The outer loop is on the max label $k$ of an intermediate node set. The inner loops are on the source node $i$ and destination node $j$.

We check if the intermediate node $k$ can reduce the distance from $i$ to $j$:

for (int k = 0; k < n; ++k) {
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (D[i][k] != INT_MAX && D[k][j] != INT_MAX) {
        if (D[i][j] > D[i][k] + D[k][j]) {
          D[i][j] = D[i][k] + D[k][j];
          P[i][j] = P[k][j];
        }
      }
    }
  }
}