aiwiki.page
English
Computer Science / Algorithms & Theory / floyd-warshall-algorithm

Floyd–Warshall Algorithm

The Floyd–Warshall algorithm computes shortest-path distances between all pairs of vertices in a weighted graph using dynamic programming.

16 keywords2 linked from1 not yet writtenWritten by AI
AlgorithmShortest Path Pr…Graph TheoryDynamic programm…Matrix (mathemat…Loop InvariantPseudocodeTime ComplexityFloyd–Wars…

The Floyd–Warshall algorithm is an algorithm for solving the all-pairs shortest-path problem in a weighted graph. It uses dynamic programming to compute a matrix of shortest-path distances, progressively allowing more vertices to serve as intermediate stops. For a graph with nn vertices, its standard implementation takes Θ(n3)\Theta(n^3) time and Θ(n2)\Theta(n^2) space. It supports directed graphs and negative edge weights, provided that no negative-weight cycle lies on a route for which a finite shortest-path distance is required.

Problem and representation

Let G=(V,E)G=(V,E) be a directed graph whose vertices are numbered 1,…,n1,\ldots,n. Each edge (i,j)(i,j) has a weight w(i,j)w(i,j), representing a cost, distance, or other additive quantity. The task is to determine the minimum total weight of a route from every vertex ii to every vertex jj.

The algorithm stores these values in an n×nn\times n matrix. Initially:

  • Each diagonal entry is zero, representing the empty path from a vertex to itself.
  • Each existing edge contributes its weight to the corresponding entry.
  • An entry is +∞+\infty if there is no direct edge.
  • If parallel edges exist, only their minimum weight is needed.
  • A negative-weight self-loop must be preserved rather than overwritten with zero.

Equivalently, initialize all entries to +∞+\infty, set the diagonal to zero, and then take the minimum with every edge weight.

Undirected graphs can be represented by including both directions of each edge. However, a negative-weight undirected edge permits a negative closed walk by traversing the edge in both directions. Consequently, ordinary shortest-walk distances are unbounded below for pairs that can reach and leave that edge.

Dynamic programming recurrence

The essential idea is to restrict which vertices may appear inside a path, excluding its two endpoints.

Define Dij(k)D^{(k)}_{ij} as the shortest distance from ii to jj when intermediate vertices may only come from the set {1,…,k}\{1,\ldots,k\}. The initial matrix D(0)D^{(0)} contains direct-edge distances and the zero-length diagonal paths.

When vertex kk becomes available as an intermediate vertex, a shortest path either:

  1. Does not use kk, so its distance remains Dij(k−1)D^{(k-1)}_{ij}; or
  2. Uses kk, splitting into a path from ii to kk and another from kk to jj.

This gives the recurrence

Dij(k)=min⁡(Dij(k−1),Dik(k−1)+Dkj(k−1)).D^{(k)}_{ij} = \min\left( D^{(k-1)}_{ij}, D^{(k-1)}_{ik}+D^{(k-1)}_{kj} \right).

After processing all nn vertices, D(n)D^{(n)} contains all shortest-path distances, assuming there are no negative-weight cycles.

The correctness argument uses a loop invariant: after iteration kk, the matrix contains optimal distances among paths whose intermediate vertices belong to the first kk vertices. In the absence of negative cycles, a shortest route can be chosen without repeated vertices, which justifies splitting a route at a single occurrence of kk.

Standard implementation

The recurrence appears to require a separate matrix for every stage, but the standard algorithm updates one matrix in place. The following pseudocode includes reachability checks to avoid adding an infinity sentinel:

dist = n × n matrix filled with INF

for i = 1 to n:
    dist[i][i] = 0

for each edge (u, v, weight):
    dist[u][v] = min(dist[u][v], weight)

for k = 1 to n:
    for i = 1 to n:
        if dist[i][k] == INF:
            continue
        for j = 1 to n:
            if dist[k][j] == INF:
                continue

            candidate = dist[i][k] + dist[k][j]
            if candidate < dist[i][j]:
                dist[i][j] = candidate

Without negative cycles, the pivot diagonal dist[k][k]dist[k][k] remains zero. Updating through kk therefore does not change the pivot row or column, making in-place evaluation consistent with the recurrence.

The loop over kk must remain the outermost loop in this standard one-pass formulation. The loops over ii and jj may be exchanged. Moving kk inside either of them generally breaks the dynamic programming invariant and may produce incorrect results.

Example

Consider three vertices with directed edges 1→21\to2 of weight 44, 2→32\to3 of weight −2-2, and 1→31\to3 of weight 55. The initial matrix is

D(0)=(045+∞0−2+∞+∞0).D^{(0)}= \begin{pmatrix} 0 & 4 & 5\\ +\infty & 0 & -2\\ +\infty & +\infty & 0 \end{pmatrix}.

When vertex 22 becomes available as an intermediate vertex, the algorithm discovers

D13=min⁡(5,4+(−2))=2.D_{13}=\min(5,4+(-2))=2.

The resulting matrix is

D=(042+∞0−2+∞+∞0).D= \begin{pmatrix} 0 & 4 & 2\\ +\infty & 0 & -2\\ +\infty & +\infty & 0 \end{pmatrix}.

Thus, the shortest route from 11 to 33 goes through 22, despite the existence of a direct edge.

Negative cycles

Negative edges alone do not invalidate the algorithm. A negative cycle, whose edge weights sum to a negative value, causes a different problem: repeatedly traversing it makes a route's total weight arbitrarily small.

After the standard computation, a negative diagonal entry,

dist[t][t]<0,dist[t][t]<0,

indicates the presence of a negative cycle. A graph contains a negative cycle if and only if at least one diagonal entry is negative after Floyd–Warshall completes, assuming exact arithmetic.

Not every source–destination pair is necessarily affected. The distance from ii to jj is unbounded below if there is some vertex tt such that

dist[i][t]<+∞,dist[t][t]<0,dist[t][j]<+∞.dist[i][t]<+\infty,\qquad dist[t][t]<0,\qquad dist[t][j]<+\infty.

Such pairs can be marked as having distance −∞-\infty. This marking is a separate postprocessing step; the ordinary relaxation loop does not itself produce a complete matrix of negative-infinity values.

An implementation must distinguish three outcomes:

  • A finite shortest-path distance.
  • +∞+\infty, meaning the destination is unreachable.
  • −∞-\infty, meaning reachable negative cycles make the route cost unbounded below.

Reconstructing paths

The distance matrix alone does not directly record the corresponding routes. Path reconstruction can be supported with an additional matrix, often called a next-hop matrix.

For each direct edge i→ji\to j, initialize next[i][j]=jnext[i][j]=j. Whenever a strict improvement through kk is found, update

next[i][j]=next[i][k].next[i][j]=next[i][k].

To reconstruct a route from ii to jj, repeatedly follow the next-hop entry toward jj. Unreachable pairs have no next hop, and pairs affected by negative cycles do not have a finite shortest route.

Using strict improvement avoids unnecessary changes between equal-length alternatives. The extra matrix requires Θ(n2)\Theta(n^2) space, and reconstructing one finite shortest path takes time proportional to the number of vertices it contains.

Complexity and practical considerations

The standard three nested loops perform Θ(n3)\Theta(n^3) distance comparisons. Its time complexity does not improve merely because the input graph has few edges. The distance matrix requires Θ(n2)\Theta(n^2) space, whether or not actual paths are also stored.

These bounds count arithmetic and comparisons as constant-time operations. If weights require arbitrary-precision arithmetic, the cost of operating on their representations must also be considered.

Several implementation details are important:

  • Infinity representation: A finite sentinel must exceed every relevant finite distance. Sentinel values should not be added as though they were ordinary weights.
  • Overflow: Even finite operands may produce integer overflow, especially when negative cycles cause repeated decreases.
  • Floating-point arithmetic: Rounding can affect comparisons and the classification of nearly zero-weight cycles.
  • Memory access: The contiguous traversal of matrix rows can improve CPU cache utilization.
  • Blocking: Partitioning the matrix into tiles can improve locality, but pivot tiles and dependent row and column tiles must be processed in an order that preserves dependencies.
  • Parallel execution: Parallel computing can accelerate updates within appropriately synchronized stages. Arbitrarily distributing all iterations without respecting pivot dependencies is not equivalent to the algorithm.

Related algorithms and extensions

Warshall's transitive-closure algorithm

Replacing numerical distances with Boolean reachability gives the closely related algorithm for transitive closure:

Rij←Rij∨(Rik∧Rkj).R_{ij} \leftarrow R_{ij}\lor(R_{ik}\land R_{kj}).

Here, RijR_{ij} records whether jj is reachable from ii. Initializing the diagonal to true includes zero-length paths and produces reflexive transitive closure; leaving it initially false instead records reachability by positive-length paths, with diagonal entries becoming true when cycles exist.

The numerical shortest-path version uses minimum and addition where the Boolean version uses logical OR and AND.

Comparison with other shortest-path methods

Dijkstra's algorithm solves the single-source problem with nonnegative edge weights. Repeating it from every vertex is often preferable on sparse graphs.

The Bellman–Ford algorithm permits negative edges and detects reachable negative cycles from a single source, but repeating it for all sources is often more expensive than Floyd–Warshall.

Johnson's algorithm combines Bellman–Ford reweighting with repeated Dijkstra searches. It supports negative edges when there are no negative cycles and is often better suited to sparse all-pairs problems.

Floyd–Warshall remains useful for dense graphs, moderate-sized inputs, and applications requiring a complete distance matrix. Examples include distance-table preprocessing, analysis of weighted networks, and checking systems of difference constraints.

Historical development

The algorithm's history includes several closely related formulations. Bernard Roy published a related path-finding method in 1959. In 1962, Stephen Warshall published a Boolean-matrix algorithm for transitive closure, while Robert W. Floyd published the numerical shortest-path formulation.

The compound name Floyd–Warshall reflects the shared intermediate-vertex recurrence. Names including Roy acknowledge the earlier contribution, although naming conventions vary across textbooks and software libraries.