Recall that the Floyd-Warshall algorithm computes shortest paths between every pair of nodes. It does so by repeatedly "combining" paths into longer ones: Given three distinct nodes a, b, c form the new path a -> c from the two paths a -> b, b -> c and check if it is an improvement.

How does this "arise" from matrix exponentiation?

Consider the following task:

A directed graph G consists of N nodes and E edges. Compute the number of (not necessarily simple) paths of length K between nodes 1 and N mod 10^9 + 7.

Constraints:
1 <= N < 100
1 <= E < n(n+1)
1 <= K < 10^9

This is a very standard problem. By exponentiating the adjacency matrix (A[i][j] = 1 if there is an edge i -> j otherwise 0) k times, we obtain a matrix B[i][j] = # of paths of length K from node i to node j.

We can prove this inductively: Denote the matrix of K-length paths to be M^K. Our base case, M^1, is trivially identical to the adjacency matrix. To prove the transition step M^a * M^b = M^a+b, consider splitting the matrices into their respective elements:

The multiplication holds if M^a+b[i][j] = sum(M^a[i][k] * M^b[k][j]) for all k. This states that the number of paths in G of length a+b from i -> j is equal to the number of ways to pick a path of length a from i -> k, and a path of length b from k -> j. It makes sense why these two quantities are equal: Every length-a+b path can be unqiuely constructed in this manner (i.e. there is a bijection).

Observe that the path-joining process implicitly used here is similar to floyd-warshall.

What if, instead of computing # of paths of specific length, we are tasked with finding (in a weighted directed graph) the shortest path 1 -> N with K nodes?

We can still build a family of "transition matrices" M^x[i][j] = shortest path i -> j with X nodes, though moving from one to the next won't be as simple as multiplication.

Consider each entry of the matrix. M^a+b[i][j] can be constructed from some combination of entries in M^a and M^b using the same bijection (each path with a+b nodes maps to a unique pair of paths with a, b nodes): M^a+b[i][j] = minimum value of M^a[i][k] + M^b[k][j] over all k.

We end up with an algorithm which resembles Floyd-Warshall.

I came across this while (finally) solving the two CSES graph mat expo problems today - my Graph Paths II code ended up looking like this:

using mat = std::array<std::array<ll, 100>, 100>;

mat mul(mat a, mat b){
    mat res = {};

    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j)
            res[i][j] = 2e18;

    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j)
            for(int k=0; k<n; ++k)
                res[i][j] = std::min(res[i][j],
                        a[i][k]+b[k][j]);

    return res;
}

of which the triple nested loop looked incredibly familiar...

tags: programming