Floyd-Warshall

All-pairs shortest paths via O(V^3) dynamic programming on the adjacency matrix.

[Graph]|

Jul 9, 2026

|explanatory_notes.md|

#floyd-warshall#all-pairs#shortest-path#dp#graph

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1e18;
const int MAXN = 505;
ll dist[MAXN][MAXN];
int n;

void init() {
    for (int i = 0; i < MAXN; i++)
        for (int j = 0; j < MAXN; j++)
            dist[i][j] = (i == j) ? 0 : INF;
}

void addEdge(int u, int v, ll w) {
    dist[u][v] = min(dist[u][v], w);
}

void floydWarshall() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

25 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Floyd-Warshall

All-pairs shortest paths in $O(V^3)$ . Works with negative weights (no negative cycles).

Recurrence

d[i][j] = \min(d[i][j],\; d[i][k] + d[k][j])

Iterate $k$ as the intermediate node over all vertices. After $k$ iterations, $d[i][j]$ is the shortest path using only vertices $\{1, \dots, k\}$ as intermediates.

When to Use

Small graphs (

V \le 500

) where you need all-pairs distances

Transitive closure (reachability)

Detecting negative cycles:

d[i][i] < 0

after the algorithm

Complexity

Time —

O(V^3)

Space —

O(V^2)