Written by Luc Haller.

Many SOI tasks are about graphs, and one of the simplest and most frequent things one wants to know about graphs is the shortest path between some pairs of vertices. You will encounter several different shortest path algorithms at SOI, but all of them solve slightly different problems. Floyd-Warshall finds the shortest path between all pairs of vertices in the graph, and the graph can have positive and negative edge weights. Breadth First Search on the other hand only works on unweighted graphs, and finds only the shortest paths from one vertex to all others. Dijkstra works on weighted graphs, but only if all edge weights are positive, and also only finds the shortest paths from one vertex to all others.

Floyd-Warshall is a typical example of an algorithm based on Dynamic Programming, but you do not need to know DP to understand Floyd-Warshall.


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 00 through N1N-1. We keep track of the length of the shortest paths in a table dd, where dk[i][j]d_k[i][j] is the length of a shortest path from ii to jj using only vertices 0,1,,k0, 1, \ldots, k. We initialize all d1[i][j]d_{-1}[i][j] to \infty, then we set for each edge (i,j)(i, j) the entry d1[i][j]d_{-1}[i][j] to the edge weight wijw_{ij}, and for each vertex ii the entry d1[i][i]d_{-1}[i][i] to 00. This is because for k=1k=-1 we only consider paths without internal vertices, which only includes vertices and edges. Then we iterate for kk from 00 to N1N-1. For each kk, we consider all i,ji, j pairs. dk1[i][j]d_{k-1}[i][j] already contains the shortest distance from ii to jj if we only use vertices 0,,k10,\ldots,k-1. The shortest path if we also allow kk as an internal vertex either does not use kk, so it was already considered, or it does use kk, in which case it consists of a shortest path from ii to kk and a shortest path from kk to jj only using vertices 0,,k0,\ldots,k internally. Since we assume that there are no negative cycles, there will be such shortest ii - kk paths and kk - jj paths which do not visit kk internally: otherwise, we could remove this extra cycle starting and ending at kk, and get a path which is at least as short. So they were actually already considered for dk1[i][j]d_{k-1}[i][j]. This shows that dk[i][j]=min(dk1[i][j],dk1[i][k]+dk1[k][j])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 vv on such a cycle, we will have found that there is a path of negative length from vv to vv, and therefore dN1[v][v]<0d_{N-1}[v][v] < 0.

So, if there are no negative cycles, dN1d_{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 dN1d_{N-1}). This could for example be done for each pair (i,j)(i, j) by looping over all vertices kk and checking if kk is reachable from ii, kk is on a negative cycle, and jj is reachable from kk (reachable: if the corresponding entry in dN1d_{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)O(1), so the running time is Θ(N3)\Theta(N^{3}). The memory usage is Θ(N2)\Theta(N^{2}), as we do not need to keep all N+1N+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 ii and jj, but also read from, this can only change entries where the shortest path contains a negative cycle (because if dk[i][k]+dk[k][j]<dk1[i][k]+dk1[k][j]d_k[i][k] + d_k[k][j] < d_{k-1}[i][k] + d_{k-1}[k][j], visiting kk multiple times made the path shorter). So all the normal distances are still computed correctly, and the criterion dN1[i][i]<0d_{N-1}[i][i] < 0 for detecting that ii is in a negative cycle also still works, and nothing of relevance has changed. This leads to the following simple 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() {

  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);
  // ....