Floyd's Algorithm

Also known as the Floyd-Warshall algorithm.

Floyd-Warshall solves the all-pairs shortest paths problem on a weighted directed graph that may contain negative edges (but no negative cycles). It is a $V^3$ dynamic program over a single $V \times V$ matrix, with a triple loop so tight it often outruns more theoretically efficient alternatives on small dense graphs.

The dynamic program is indexed by $k = 0, 1, \dots, n$, where $dist_k[i][j]$ is the length of the shortest $i$-to-$j$ path whose intermediate vertices (all vertices on the path other than its two endpoints) all come from the first $k$ indices $0, 1, \dots, k-1$. At $k = 0$ the only allowed paths are the direct edges; at $k = n$ every vertex is allowed as an intermediate, which is exactly the unrestricted shortest path. The update rule at step $k$ asks, for each pair $(i, j)$, whether routing through vertex $k - 1$ is better than not using it.

The solve function takes [n, edges] with edges as [u, v, w] triples and returns the $n \times n$ all-pairs distance matrix, using 10**18 for unreachable pairs.

Codes

Python

Original reusable helper:

def floydWarshall(edges,n,inf:int=10**9,is_bidirectional:bool=False):
    # return minDistance of all 
    minD=[[0 if i==j else inf for i in range(n)] for j in range(n)]
    for a,b,w in edges:
        minD[a][b]=min(minD[a][b],w)
        if is_bidirectional: minD[b][a]=min(minD[a][b],w)
    for k in range(n):
        for a in range(n):
            if a==k: continue
            for b in range(n):
                if a==b or b==k: continue
                minD[a][b]=min(minD[a][b],minD[a][k]+minD[k][b])
    return minD

Cleaned up solve form:

def solve(xs):
    """xs = [n, edges]. Return the all-pairs distance matrix."""
    n, edges = xs
    INF = 10**18
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        if w < dist[u][v]:
            dist[u][v] = w
    for k in range(n):
        dk = dist[k]
        for i in range(n):
            di = dist[i]
            dik = di[k]
            if dik == INF:
                continue
            for j in range(n):
                nd = dik + dk[j]
                if nd < di[j]:
                    di[j] = nd
    return dist

C++

#include <array>
#include <vector>

const long long INF = (long long)1e18;

std::vector<std::vector<long long>> floyd_warshall(
        int n, const std::vector<std::array<int, 3>>& edges) {
    std::vector<std::vector<long long>> dist(n, std::vector<long long>(n, INF));
    for (int i = 0; i < n; ++i) dist[i][i] = 0;
    for (auto& e : edges) {
        if (e[2] < dist[e[0]][e[1]]) dist[e[0]][e[1]] = e[2];
    }
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i) {
            if (dist[i][k] == INF) continue;
            for (int j = 0; j < n; ++j) {
                long long nd = dist[i][k] + dist[k][j];
                if (nd < dist[i][j]) dist[i][j] = nd;
            }
        }
    return dist;
}

Example

Loading Python runner...

Description

Floyd's algorithm, also known as the Floyd-Warshall algorithm, is a dynamic programming algorithm used to find the shortest paths between all pairs of nodes in a weighted graph. It can handle graphs with negative edge weights but no negative cycles.

The algorithm works by iteratively considering each node as an intermediate point and updating the shortest paths between all pairs of nodes based on whether passing through the intermediate node offers a shorter path.

Run time analysis

$O(V^3)$. The algorithm is three nested loops of length $V$ with a constant-time relaxation inside. The bound is tight: the triple loop touches each matrix cell $V$ times.

Space analysis

$O(V^2)$. A single distance matrix is kept; the update is performed in place because the row and column indexed by $k$ never change during phase $k$ (see the proof), so overwriting them is safe.

Proof of correctness

Define $D_k[i][j]$ as the length of the shortest $i$-to-$j$ walk whose intermediate vertices are drawn from the first $k$ vertices $0, 1, \dots, k-1$, or $\infty$ if no such walk exists. We prove by induction on $k$ that after the $k$-th outer iteration the matrix $dist$ equals $D_k$.

Base case ($k = 0$). Before any outer iteration, $dist[i][j]$ is the weight of the direct edge from $i$ to $j$ (or $0$ on the diagonal, or $\infty$ otherwise). These are exactly the walks with no intermediate vertex allowed, matching $D_0$.

Inductive step. Suppose $dist = D_{k-1}$ before the outer iteration for $k - 1$ (our $k$ in $0$-based indexing). Consider a shortest $i$-to-$j$ walk whose intermediate vertices come from the first $k$ indices. It either uses vertex $k - 1$ as an intermediate or it does not.

• If it does not, its intermediates lie in the first $k - 1$ indices, so its length equals $D_{k-1}[i][j]$.
• If it does, we can split it at its first visit to $k - 1$ into an $i$-to-$(k-1)$ walk and a $(k-1)$-to-$j$ walk, each using only intermediates in the first $k - 1$ indices. (If the walk visited $k - 1$ more than once, the loop between the first and last visit has nonnegative weight — by assumption there are no negative cycles — and cutting it out cannot increase the length.) So the length is $D_{k-1}[i][k-1] + D_{k-1}[k-1][j]$.

The minimum of these two options is exactly the update rule $dist[i][j] \gets \min(dist[i][j],\ dist[i][k-1] + dist[k-1][j])$. In-place update is safe because during the $k$-th phase neither $dist[i][k-1]$ nor $dist[k-1][j]$ is ever overwritten by the update rule (an update writes to $dist[i][j]$ with $j = k - 1$ only when $dist[i][k-1] + dist[k-1][k-1] < dist[i][k-1]$, which cannot happen since $dist[k-1][k-1] = 0$ in the no-negative-cycle case; analogously for $i = k - 1$). So after the $k$-th phase $dist = D_k$, completing the induction.

After the $n$-th phase $dist = D_n$, which allows every vertex as an intermediate, so $dist[i][j]$ is the true shortest-walk length.

Extensions

Applications

LeetCode 2976 [Expected difficulty: 7]

link to problem

Intuition

We may compute the cost for converting each character to every other character using Floyd's algorithm, then use iteration to calculate the total cost for each string in words.

Solution

Generally in most cases, the Dijkstra's algorithm would be more efficient for single-source shortest path problems. However, in this specific problem, in worst case, we need to compute the shortest paths between all pairs of characters (from 'a' to 'z') to determine the minimum conversion costs. Floyd-Warshall is well-suited for this all-pairs shortest path requirement, especially given the limited number of characters (26 letters).

Thus, using Floyd-Warshall simplifies the implementation and ensures we have the minimum costs readily available for any character conversion needed in the words.

class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        def floydWarshall(edges,n,inf:int=10**9,is_bidirectional:bool=False):
            # return minDistance of all 
            minD=[[0 if i==j else inf for i in range(n)] for j in range(n)]
            for a,b,w in edges:
                minD[a][b]=min(minD[a][b],w)
                if is_bidirectional: minD[b][a]=min(minD[a][b],w)
            for k in range(n):
                for a in range(n):
                    if a==k: continue
                    for b in range(n):
                        if a==b or b==k: continue
                        minD[a][b]=min(minD[a][b],minD[a][k]+minD[k][b])
            return minD
        inf=10**9+1
        n=26
        m=len(source)
        adj=floydWarshall(zip(map(lambda x: ord(x)-ord('a'),original),map(lambda x: ord(x)-ord('a'),changed),cost),n,inf=inf)
        # print(adj)
        res=0
        for i in range(m):
            d=adj[ord(source[i])-ord('a')][ord(target[i])-ord('a')]
            # print(ord(source[i])-ord('a'),ord(target[i])-ord('a'),d)
            if d==inf: return -1
            res+=d
        return res

References

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 3rd ed., Chapter 25 (All-Pairs Shortest Paths).
• Floyd, R. W. (1962). "Algorithm 97: Shortest path." Communications of the ACM, 5(6), 345.
• cp-algorithms — Floyd-Warshall