Algorithms and data structures · Intermediate

Floyd–Warshall: grow the allowed intermediate set

Compute all-pairs distances with a matrix recurrence while respecting the intermediate-vertex invariant and negative-cycle scope.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Store distances for every ordered pair
  2. Trace an intermediate improvement
  3. Classify the effect of negative cycles
  4. Choose the matrix cost deliberately
  5. Ask Logeia about this articleCheck your understanding

Store distances for every ordered pair

Floyd–Warshall computes a distance matrix for all ordered vertex pairs. Initialize direct edges with their weights, diagonal entries with zero when appropriate, and absent connections with infinity. Use the minimum of parallel edge weights and do not accidentally erase a negative self-loop. At stage k, allow vertex k as an additional intermediate vertex and test whether d[i][k]+d[k][j] improves d[i][j]. The proof depends on what intermediate vertices are allowed in each stage. Merely writing three nested loops does not establish that invariant or guarantee a correct distance matrix.

Trace an intermediate improvement

Take directed edges A→B of weight 3, B→C of weight −1 and A→C of weight 5. When B becomes an allowed intermediate vertex, the A-to-C distance improves to 2. C-to-A remains unreachable. Making the matrix symmetric would silently turn this into a different graph. In the standard in-place algorithm, k is the outermost loop and every i,j pair is updated inside it. Simply moving i or j outside changes the meaning of the intermediate state and does not generally preserve the all-pairs shortest-path recurrence.

Classify the effect of negative cycles

Negative edges can be handled, but a pair whose paths can pass through a negative cycle has no finite minimum distance. After the updates, a negative diagonal d[k][k] identifies the presence of such a cycle. If i can reach k and k can reach j, traversing that cycle repeatedly makes an i-to-j walk arbitrarily cheap. Unreachable components should not automatically receive the same classification. Also distinguish an API that only reports that some negative cycle exists from one that classifies which individual vertex pairs have unbounded distances.

Choose the matrix cost deliberately

A V-by-V matrix and a complete i,j update for each k give O(V³) time and O(V²) distance storage. Reconstructing actual paths requires additional next-hop or predecessor information. Only add finite distances, and guard arithmetic overflow instead of relying on a finite integer sentinel to behave like mathematical infinity. A few-source query workload or a very large sparse graph may call for a different shortest-path method. For a modest dense all-pairs problem, however, the explicit matrix recurrence is easy to state, test and compare with the graph’s reachability structure.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 11

Choose a learning path