Floyd-Warshall (All-Pairs Shortest Paths)

DSA · Graphs

Theory

Floyd-Warshall finds the shortest distance between every pair of vertices in a weighted graph. It uses dynamic programming: dist[i][j] starts as the direct edge weight (or infinity), and the algorithm then tries every vertex k as an intermediate stop, updating dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). After considering all k, the table contains the shortest path for every pair. It works with negative edge weights as long as there is no negative cycle, and a negative value on the diagonal (dist[i][i] < 0) reveals such a cycle. With three nested loops it runs in O(V^3), so it suits graphs with up to a few hundred vertices.

Why we use it

When you need distances between all pairs, running Dijkstra from every vertex is more code and, on dense graphs, no faster. Floyd-Warshall is short, handles negative weights and detects negative cycles.

When to use it

Use it for small or dense graphs when all-pairs distances are needed, such as a distance table between cities or transitive closure. Use Dijkstra for one source on large sparse graphs.

How it works

  1. dist = adjacency matrix
  2. For each intermediate k
  3. For each pair (i, j)
  4. dist[i][k] + dist[k][j] < dist[i][j]? Yes: Update dist[i][j]. No: Keep.
  5. All-pairs shortest paths in O(V^3)

Syntax

for k in V:
  for i in V:
    for j in V:
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
Time O(V^3)   Space O(V^2)

Example

INF = float("inf")
cities = ["Delhi", "Jaipur", "Agra", "Lucknow"]
# adjacency matrix of road distances (km); INF = no direct road
dist = [
    [0,   280, 230, INF],
    [280, 0,   240, INF],
    [230, 240, 0,   335],
    [INF, INF, 335, 0],
]
n = len(dist)
for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

print(f"{'':8}" + "".join(f"{c:>9}" for c in cities))
for i, row in enumerate(dist):
    print(f"{cities[i]:8}" + "".join(f"{d:>9}" for d in row))
print("Negative cycle?", any(dist[i][i] < 0 for i in range(n)))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic