Floyd-Warshall finds the shortest path between every pair of vertices using Dynamic Programming.

Its biggest advantage is:

One algorithm computes shortest paths between all pairs of vertices.

It also supports negative edge weights, as long as there is no negative cycle affecting the paths we care about.

Focus on recognizing:

“All pairs shortest path” + “small/dense graph” = Floyd-Warshall

Pattern Table

Pattern	Typical Questions	Trigger
All-Pairs Shortest Path	Distance between every pair	All pairs
Reachability	Can `i` reach `j`?	Transitive closure
Negative Cycle Detection	Is there a negative cycle?	`dist[i][i] < 0`
Intermediate Constraints	Best path through nodes	DP over intermediates

Mental Trigger

Intermediate Node + DP Matrix + Triple Loop → Floyd-Warshall

The key question is:

“What is the shortest path from i to j if I am allowed to use nodes 0...k as intermediates?“

1. Generic Floyd-Warshall Template (Base)

This is the main template you should memorize.

One via-node k, one dramatic improvement — this is the entire k-outer-loop insight in six steps:

Floyd-Warshall

Shortest path between EVERY pair of nodes.

Outer loop is the via-node k; inner loops try dist[i][k]+dist[k][j] < dist[i][j]. k MUST be outermost so shorter paths are available before they're used. O(V³) yields the full distance matrix.

GRAPH VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dist[i][j] = direct edge or ∞; dist[i][i] = 0
                      
                        2
                        for k in all nodes:        // via-node FIRST
                      
                        3
                          for i, for j:
                      
                        4
                            if dist[i][k] + dist[k][j] < dist[i][j]:
                      
                        5
                              dist[i][j] = dist[i][k] + dist[k][j]

public long[][] floydWarshall(int n, int[][] edges) {
    final long INF = Long.MAX_VALUE / 4;

    long[][] dist = new long[n][n];

    for (int i = 0; i < n; i++) {
        Arrays.fill(dist[i], INF);
        dist[i][i] = 0;
    }

    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        int weight = edge[2];

        dist[u][v] = Math.min(dist[u][v], weight);
    }

    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++) {

                if (dist[k][j] == INF) {
                    continue;
                }

                dist[i][j] = Math.min(
                    dist[i][j],
                    dist[i][k] + dist[k][j]
                );
            }
        }
    }

    return dist;
}

def floyd_warshall(n, edges):
    INF = float('inf')

    dist = [[INF] * n for _ in range(n)]

    for i in range(n):
        dist[i][i] = 0

    for u, v, weight in edges:
        dist[u][v] = min(dist[u][v], weight)

    for k in range(n):
        for i in range(n):

            if dist[i][k] == INF:
                continue

            for j in range(n):

                if dist[k][j] == INF:
                    continue

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

    return dist

vector<vector<long long>> floydWarshall(int n, vector<vector<int>>& edges) {
    const long long INF = LLONG_MAX / 4;

    vector<vector<long long>> dist(
        n, vector<long long>(n, INF));

    for (int i = 0; i < n; i++) {
        dist[i][i] = 0;
    }

    for (auto& edge : edges) {
        int u = edge[0];
        int v = edge[1];
        int weight = edge[2];

        dist[u][v] = min(dist[u][v], (long long)weight);
    }

    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++) {

                if (dist[k][j] == INF) {
                    continue;
                }

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

    return dist;
}

function floydWarshall(n, edges) {
  const INF = Infinity;

  const dist = Array.from({ length: n }, () =>
    new Array(n).fill(INF)
  );

  for (let i = 0; i < n; i++) {
    dist[i][i] = 0;
  }

  for (const [u, v, weight] of edges) {
    dist[u][v] = Math.min(dist[u][v], weight);
  }

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      if (dist[i][k] === INF) continue;

      for (let j = 0; j < n; j++) {
        if (dist[k][j] === INF) continue;

        dist[i][j] = Math.min(
          dist[i][j],
          dist[i][k] + dist[k][j]
        );
      }
    }
  }

  return dist;
}

Everything else is a modification of this DP template.

Why the `k` Loop Comes First

The most important part is:

for (int k = 0; k < n; k++)

k represents the set of intermediate vertices currently allowed.

For every pair (i, j):

Do we get a shorter path:

i → j

or

i → k → j ?

So the transition is:

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

Floyd-Warshall = Try every vertex as an intermediate node.

Pattern 1: All-Pairs Shortest Path

Problem Type

Use Floyd-Warshall when:

You need distances between many pairs.
The graph is relatively small.
Edge weights may be negative.
You want a simple O(V³) solution.

Java Code

public long shortestDistance(
        long[][] dist,
        int source,
        int destination) {

    return dist[source][destination];
}

def shortest_distance(dist, source, destination):
    return dist[source][destination]

long long shortestDistance(
        vector<vector<long long>>& dist,
        int source,
        int destination) {

    return dist[source][destination];
}

function shortestDistance(dist, source, destination) {
  return dist[source][destination];
}

What Changed from the Base Template?

Nothing.

The base algorithm already computes:

dist[i][j]

for every pair.

So after preprocessing:

dist[u][v]

answers the shortest-path query directly.

All-pairs shortest path = Build the matrix once, answer queries in O(1).

Pattern 2: Direct Edge Initialization

One subtle but important detail is handling multiple edges between the same vertices.

Wrong

dist[u][v] = weight;

Suppose the graph contains:

0 → 1 = 10
0 → 1 = 3

The correct initial value is:

Correct

dist[u][v] = Math.min(dist[u][v], weight);

Why?

The direct edge itself is a possible path.

We should keep the cheapest direct edge.

Multiple edges → initialize with the minimum weight.

Pattern 3: Detect Negative Cycles

Floyd-Warshall can detect negative cycles after the DP finishes.

Key Idea

Normally:

dist[i][i] = 0;

because the distance from a node to itself is zero.

But if we discover:

dist[i][i] < 0

then there is a negative cycle reachable from i.

Java Code

public boolean hasNegativeCycle(long[][] dist) {

    for (int i = 0; i < dist.length; i++) {
        if (dist[i][i] < 0) {
            return true;
        }
    }

    return false;
}

def has_negative_cycle(dist):

    for i in range(len(dist)):
        if dist[i][i] < 0:
            return True

    return False

bool hasNegativeCycle(vector<vector<long long>>& dist) {

    for (int i = 0; i < (int)dist.size(); i++) {
        if (dist[i][i] < 0) {
            return true;
        }
    }

    return false;
}

function hasNegativeCycle(dist) {
  for (let i = 0; i < dist.length; i++) {
    if (dist[i][i] < 0) {
      return true;
    }
  }

  return false;
}

What Changed from the Base Template?

Added a final diagonal check:

dist[i][i] < 0

Negative diagonal value = negative cycle.

Pattern 4: Reachability / Transitive Closure

Floyd-Warshall can also answer:

“Can vertex i reach vertex j?”

We don’t need actual distances.

We only store:

true / false

Java Code

public boolean[][] transitiveClosure(
        int n,
        int[][] edges) {

    boolean[][] reachable = new boolean[n][n];

    for (int i = 0; i < n; i++) {
        reachable[i][i] = true;
    }

    for (int[] edge : edges) {
        reachable[edge[0]][edge[1]] = true;
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {

            if (!reachable[i][k]) {
                continue;
            }

            for (int j = 0; j < n; j++) {

                reachable[i][j] =
                    reachable[i][j]
                    || reachable[k][j];
            }
        }
    }

    return reachable;
}

def transitive_closure(n, edges):
    reachable = [[False] * n for _ in range(n)]

    for i in range(n):
        reachable[i][i] = True

    for u, v in edges:
        reachable[u][v] = True

    for k in range(n):
        for i in range(n):

            if not reachable[i][k]:
                continue

            for j in range(n):
                reachable[i][j] = (
                    reachable[i][j]
                    or reachable[k][j]
                )

    return reachable

vector<vector<bool>> transitiveClosure(int n, vector<vector<int>>& edges) {
    vector<vector<bool>> reachable(
        n, vector<bool>(n, false));

    for (int i = 0; i < n; i++) {
        reachable[i][i] = true;
    }

    for (auto& edge : edges) {
        reachable[edge[0]][edge[1]] = true;
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {

            if (!reachable[i][k]) {
                continue;
            }

            for (int j = 0; j < n; j++) {

                reachable[i][j] =
                    reachable[i][j]
                    || reachable[k][j];
            }
        }
    }

    return reachable;
}

function transitiveClosure(n, edges) {
  const reachable = Array.from({ length: n }, () =>
    new Array(n).fill(false)
  );

  for (let i = 0; i < n; i++) {
    reachable[i][i] = true;
  }

  for (const [u, v] of edges) {
    reachable[u][v] = true;
  }

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      if (!reachable[i][k]) continue;

      for (let j = 0; j < n; j++) {
        reachable[i][j] =
          reachable[i][j] || reachable[k][j];
      }
    }
  }

  return reachable;
}

What Changed from the Base Template?

Distance:

dist[i][j]

becomes reachability:

reachable[i][j]

And the transition:

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

becomes:

reachable[i][j] =
    reachable[i][j]
    || reachable[i][k] && reachable[k][j];

Same triple-loop structure, different DP state.

Pattern 5: Find the Shortest Path Through an Intermediate

Problem Type

Sometimes the problem asks:

“What is the shortest path from i to j through k?”

After Floyd-Warshall:

long distance = dist[i][k] + dist[k][j];

If both paths exist.

Java Code

public long pathThrough(
        long[][] dist,
        int i,
        int k,
        int j) {

    final long INF = Long.MAX_VALUE / 4;

    if (dist[i][k] == INF || dist[k][j] == INF) {
        return INF;
    }

    return dist[i][k] + dist[k][j];
}

def path_through(dist, i, k, j):
    INF = float('inf')

    if dist[i][k] == INF or dist[k][j] == INF:
        return INF

    return dist[i][k] + dist[k][j]

long long pathThrough(
        vector<vector<long long>>& dist,
        int i,
        int k,
        int j) {

    const long long INF = LLONG_MAX / 4;

    if (dist[i][k] == INF || dist[k][j] == INF) {
        return INF;
    }

    return dist[i][k] + dist[k][j];
}

function pathThrough(dist, i, k, j) {
  const INF = Infinity;

  if (dist[i][k] === INF || dist[k][j] === INF) {
    return INF;
  }

  return dist[i][k] + dist[k][j];
}

Floyd-Warshall stores the best answer for every possible intermediate set.

Pattern Evolution

Basic DP Matrix
      ↓
Initialize direct edges
      ↓
Try every intermediate k
      ↓
Relax every pair (i, j)
      ↓
All-Pairs Shortest Path
      ↓
Negative Cycle Detection
      ↓
Transitive Closure

Visual Intuition

Suppose:

A → B = 5
B → C = 2
A → C = 10

Initially:

dist[A][C] = 10

Now consider:

k = B

We compare:

A → C

with:

A → B → C

5 + 2 = 7

So:

dist[A][C] = min(10, 7)
            = 7

The Core Transition

Always remember:

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

Think:

Current best
     ↓
i ─────────→ j
 \          ↑
  \         |
   → k ─────

Ask:

“Is going through k cheaper?”

Why Floyd-Warshall Is Dynamic Programming

The DP state is:

dist[i][j]

meaning:

shortest distance from i to j using the currently allowed intermediate vertices.

When we introduce vertex k, there are only two possibilities:

Don’t use `k`

dist[i][j]

Use `k`

dist[i][k] + dist[k][j]

Therefore:

new answer =
min(old answer, path through k)

Common Mistakes

Wrong Loop Order

Wrong:

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        for (int k = 0; k < n; k++)

Correct:

for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)

k must be the outermost loop because it represents the newly allowed intermediate vertex.

Overflowing INF

Wrong:

dist[i][k] + dist[k][j]

when either value is INF.

Correct:

if (dist[i][k] == INF ||
    dist[k][j] == INF) {
    continue;
}

Also prefer a safe long sentinel:

final long INF = Long.MAX_VALUE / 4;

instead of:

Integer.MAX_VALUE

Forgetting `dist[i][i] = 0`

Correct initialization:

dist[i][i] = 0;

Every vertex has a zero-cost path to itself before considering cycles.

Overwriting Duplicate Edges

Wrong:

dist[u][v] = weight;

Correct:

dist[u][v] = Math.min(dist[u][v], weight);

Assuming Floyd-Warshall Cannot Handle Negative Edges

It can.

For example:

A → B = 5
B → C = -3

is completely valid.

The problem is a negative cycle, not merely a negative edge.

Forgetting Negative Cycle Detection

After the algorithm:

for (int i = 0; i < n; i++) {
    if (dist[i][i] < 0) {
        // negative cycle exists
    }
}

Complexity

For V vertices:

Time:  O(V³)
Space: O(V²)

This makes Floyd-Warshall especially useful when:

V is relatively small.
Many source-destination queries exist.
The graph is dense.
You need all-pairs information.

The exact practical limit depends on the language, hardware, and time limit; V ≈ 500 is a common competitive-programming scale, not a universal hard limit.

Floyd-Warshall vs BFS vs Dijkstra vs Bellman-Ford

Feature	BFS	Dijkstra	Bellman-Ford	Floyd-Warshall
Unweighted graph	✅	✅	✅	✅
Non-negative weights	❌*	✅	✅	✅
Negative edges	❌	❌	✅	✅
Negative cycle detection	❌	❌	✅	✅
Single-source shortest path	✅	✅	✅	⚠️
All-pairs shortest path	❌	Repeated runs	Repeated runs	✅
Main structure	Queue	Priority Queue	Edge relaxation	DP matrix
Time	`O(V + E)`	`O((V + E) log V)`	`O(VE)`	`O(V³)`
Space	`O(V)`	`O(V + E)`	`O(V)`	`O(V²)`

* BFS is specifically appropriate for unweighted shortest paths.

Recognition Cheat Sheet

If you see…	Think…
All pairs shortest path	Floyd-Warshall
Distance between every pair	Floyd-Warshall
Many shortest-path queries	Floyd-Warshall
Small/dense graph	Floyd-Warshall
Negative edges + all pairs	Floyd-Warshall
Negative cycle detection	Floyd-Warshall / Bellman-Ford
Can `i` reach `j`?	Transitive closure
One source + non-negative weights	Dijkstra
One source + negative edges	Bellman-Ford
Unweighted shortest path	BFS

Earn Premium with Referrals

Pattern Table

Mental Trigger

1. Generic Floyd-Warshall Template (Base)

Floyd-Warshall

Why the k Loop Comes First

Pattern 1: All-Pairs Shortest Path

Problem Type

Java Code

What Changed from the Base Template?

Pattern 2: Direct Edge Initialization

Wrong

Correct

Why?

Pattern 3: Detect Negative Cycles

Key Idea

Java Code

What Changed from the Base Template?

Pattern 4: Reachability / Transitive Closure

Java Code

What Changed from the Base Template?

Pattern 5: Find the Shortest Path Through an Intermediate

Problem Type

Java Code

Pattern Evolution

Visual Intuition

The Core Transition

Why Floyd-Warshall Is Dynamic Programming

Don’t use k

Use k

Common Mistakes

Wrong Loop Order

Overflowing INF

Forgetting dist[i][i] = 0

Overwriting Duplicate Edges

Assuming Floyd-Warshall Cannot Handle Negative Edges

Forgetting Negative Cycle Detection

Complexity

Floyd-Warshall vs BFS vs Dijkstra vs Bellman-Ford

Recognition Cheat Sheet

Premium Content

My Private Notes

Why the `k` Loop Comes First

Don’t use `k`

Use `k`

Forgetting `dist[i][i] = 0`