CoreSource checked

Floyd-Warshall

Finds shortest paths between every pair of nodes.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pathfinding
Difficulty: Intermediate
Family: Dynamic Programming
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 4
Code example: Not ready
Visualization: Ready

Overview

Floyd-Warshall improves a distance table by checking whether each node is a useful intermediate stop.

Core Concepts

all-pairs distance tableintermediate nodesdynamic programmingpath relaxationdistance relaxationall-pairs tablegraph representationroute cost

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(V^3)

Average

O(V^3)

Worst

O(V^3)

Space

O(V^2)

When to Use

Use Floyd-Warshall when you need to compute all-pairs shortest paths.
Use it for dense graph analysis with inputs like weighted graph as a distance matrix.
Use it when routes have explicit movement rules, costs, obstacles, or graph edges.
Use it when the Dynamic Programming tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when the state table would exceed available memory.
Avoid it when edge costs or movement constraints do not match the algorithm's assumptions.
Avoid it when O(V^3) worst-case behavior is too costly for the expected input size.
Avoid it when the required output is not all-pairs shortest distance matrix.

What It Does

Computes all-pairs shortest paths
Updates distances through intermediate nodes

Use Cases

Dense graph analysis
Small all-pairs routing tables
Finding graph reachability variants

Inputs

Weighted graph as a distance matrix

Outputs

All-pairs shortest distance matrix

Key Formulas (1)

Intermediate-node update

dist_[i]_[j] = min(dist_[i]_[j], dist_[i]_[k] + dist_[k]_[j])

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Checks whether routing through node k improves the best known path from i to j.

Pseudocode

1.Start with a matrix of direct edge distances
2.For each possible intermediate node:
3.Check every start and end pair
4.Replace the known distance if going through the intermediate is cheaper
5.Return the final distance matrix

Canonical Example

Input: edges = A-B: 1, B-C: 2, A-C: 5; start = A; goal = C
Output: path = A -> B -> C, cost = 3
Explanation: Floyd-Warshall: The algorithm compares route costs and selects the cheaper path through B.

Implementation Notes

Keep the input contract explicit: Weighted graph as a distance matrix.
Use this step as the implementation spine: Start with a matrix of direct edge distances.
Then preserve the next state change: For each possible intermediate node:.
Keep node ids, edge direction, and visited state explicit in the implementation.

Common Pitfalls

Floyd-Warshall is simple and compact but expensive for large graphs.
Not defining directed versus undirected edges clearly can change the result.
Treating a visited node as final before its best known cost is actually settled.
Handle empty, invalid, and boundary inputs before trusting all-pairs shortest distance matrix.

Interactive Mechanism Walkthrough

2D Grid Wavefront & Trajectory

Show a distance matrix improving as each intermediate node is considered.

Step 1 of 5: Start with a matrix of direct edge distances

distance-matrix

Notes

Floyd-Warshall operates in O(V^3) time and O(V^2) space within the Dynamic Programming family. Key governing relation: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Often compared with Bellman-Ford and Dijkstra's Algorithm.