Floyd-Warshall

Idea

The basic idea is that we iteratively compute shortest paths which only use a subset of vertices as intermediate vertices, starting with the empty set and ending with the set of all vertices, meaning that we have considered all paths. The reason for computing them this way is that we can use the shortest paths from the previous iteration to easily compute the ones for the current iteration (therefore it’s DP).

In this section, we assume that there are no cycles with negative total length in the graph. Later we will explain why and what changes if we allow negative cycles.

As usual we assume that the vertices of the graph are numbered $0$ through $N-1$. We keep track of the length of the shortest paths in a table $d$, where $d_k[i][j]$ is the length of a shortest path from $i$ to $j$ using only vertices $0, 1, \ldots, k$. We initialize all $d_{-1}[i][j]$ to $\infty$, then we set for each edge $(i, j)$ the entry $d_{-1}[i][j]$ to the edge weight $w_{ij}$, and for each vertex $i$ the entry $d_{-1}[i][i]$ to $0$. This is because for $k=-1$ we only consider paths without internal vertices, which only includes vertices and edges. Then we iterate for $k$ from $0$ to $N-1$. For each $k$, we consider all $i, j$ pairs. $d_{k-1}[i][j]$ already contains the shortest distance from $i$ to $j$ if we only use vertices $0,\ldots,k-1$. The shortest path if we also allow $k$ as an internal vertex either does not use $k$, so it was already considered, or it does use $k$, in which case it consists of a shortest path from $i$ to $k$ and a shortest path from $k$ to $j$ only using vertices $0,\ldots,k$ internally. Since we assume that there are no negative cycles, there will be such shortest $i$ - $k$ paths and $k$ - $j$ paths which do not visit $k$ internally: otherwise, we could remove this extra cycle starting and ending at $k$, and get a path which is at least as short. So they were actually already considered for $d_{k-1}[i][j]$. This shows that $d_k[i][j] = \min(d_{k-1}[i][j], d_{k-1}[i][k] + d_{k-1}[k][j])$.

Negative Cycles

Above, we assumed that there are no cycles with negative total length, and used this assumption to show that there is always a shortest path containing no vertex twice. If, on the other hand, there are negative cycles, all paths touching such a cycle can be made shorter by going once more around the cycle. Therefore, the length of such paths can be made arbitrarily negative, and the distance between their endpoints is $-\infty$.

It is easy to detect whether there are any negative cycles in a graph after we have run Floyd-Warshall: For each vertex $v$ on such a cycle, we will have found that there is a path of negative length from $v$ to $v$, and therefore $d_{N-1}[v][v] < 0$.

So, if there are no negative cycles, $d_{N-1}$ gives us the distance between each pair of vertices. Otherwise, it can tell us which vertices are in negative cycles. Most tasks do not require more than this, but it is also possible to determine the distances in the general case (that is, find for which pairs it is $-\infty$ instead of the entry in $d_{N-1}$). This could for example be done for each pair $(i, j)$ by looping over all vertices $k$ and checking if $k$ is reachable from $i$, $k$ is on a negative cycle, and $j$ is reachable from $k$ (reachable: if the corresponding entry in $d_{N-1}$ is less than $+\infty$).

Running Time and Memory Usage

We have three nested loops over all vertices, and the body of the innermost loop runs in $O(1)$, so the running time is $\Theta(N^{3})$. The memory usage is $\Theta(N^{2})$, as we do not need to keep all $N+1$ versions of the distance matrix. Note that we don’t even need to keep the previous and the current version: If we only keep one version, which we overwrite during the loops over $i$ and $j$, but also read from, this can only change entries where the shortest path contains a negative cycle (because if $d_k[i][k] + d_k[k][j] < d_{k-1}[i][k] + d_{k-1}[k][j]$, visiting $k$ multiple times made the path shorter). So all the normal distances are still computed correctly, and the criterion $d_{N-1}[i][i] < 0$ for detecting that $i$ is in a negative cycle also still works, and nothing of relevance has changed. This leads to the following simple implementation.

Implementation

#include <iostream> //cin, cout
#include <vector> //vector

using namespace std;

struct Edge {
  int from;
  int to;
  int length;
};

const int INF = 1e9;

vector<vector<int>> floyd_warshall(int n, const vector<Edge>& edges) {
  // initializing the distance matrix
  vector<vector<int>> d(n, vector<int>(n, INF));
  for (int i=0; i<n; ++i)
    d[i][i] = 0;
  for (const auto& e: edges)
    d[e.from][e.to] = min(d[e.from][e.to], e.length);

  // iterating
  for (int k=0; k<n; ++k) {
    for (int i=0; i<n; ++i) {
      for (int j=0; j<n; ++j) {
        int newdij = d[i][k] + d[k][j];
        if (newdij < d[i][j])
          d[i][j] = newdij;
      }
    }
  }

  return d;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;
  vector<Edge> edges;
  for (int i=0; i<m; ++i) {
    int from, to, length;
    cin >> from >> to >> length;
    edges.push_back({from, to, length});
  }

  vector<vector<int>> d = floyd_warshall(n, edges);
  // ....
}