All pairs shortest path (Floyd's)

Abhijeet Singh Rajput

@abhijeetsingh

Created

Nov 15, 2025

Last Modified

2 weeks ago

All Pairs Shortest Path (Floyd-Warshall Algorithm)

Introduction

For a given connected weighted graph $G (V, E)$ , the All Pairs Shortest Path (APSP) problem aims to find the shortest path between every pair of vertices.

Floyd–Warshall is a classic algorithm for solving All Pairs Shortest Path.
It works for both directed and undirected graphs, as long as the graph does not contain a negative cycle.

Weight Matrix

Let the weight matrix be:

W = [w_{ij}]_{n \times n}

Each entry is:

w_{ij} = {c_{ij}, \infty, if vertex i is adjacent to j otherwise

Where:

$c_{ij}$ = weight of edge $(i, j)$
$c_{ii} = 0$

Distance Matrices

The algorithm computes a series of matrices:

D^{0}, D^{1}, D^{2}, \cdot \cdot \cdot, D^{n}

Here:

$D^{k}$ stores the shortest path distances between every pair $(i, j)$
Intermediate vertices allowed must be numbered ≤ k

So,

D^{k} = [d_{ij}^{k}]_{n \times n}

Recursive Relation

Each entry in matrix $D^{k}$ is computed using values from $D^{k - 1}$ :

d_{ij}^{k} = min {d_{ij}^{k - 1}, d_{ik}^{k - 1} + d_{k j}^{k - 1}}

Interpretation:

First value: shortest path from $i \to j$ without using vertex $k$
Second value: shortest path from $i \to j$ using vertex $k$
We pick the shorter one.

Meaning

For step $k$ , we check whether including vertex $k$ as an intermediate point gives a shorter route between every pair $(i, j)$ . If yes, update it.

Algorithm

cpp

floydWarshall(weightMatrix[n][n])
{
    // Input :    Weight matrix W for given weighted connected graph G(V, E)
    // Output :    D the distance matrix

    for k = 1 to n do
    {
        for i = 1 to n do
        {
            for j = 1 to n do
            {
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
            }
        }
    }
    return D
}

The time complexity of algorithm is big $O (n^{3})$ since there are three nested loop each with an iteration

For the given problem, the number of nodes is: $N = 4$

The graph is a directed weighted graph.
We first construct the weight matrix $W$ for the given graph.

W = D^{0} = 02 \infty 6 \infty 07 \infty 3 \infty 0 \infty \infty \infty 10

Recursive Relation

To compute $D^{k}$ from $D^{k - 1}$ :

d_{ij}^{k} = min (d_{ij}^{k - 1}, d_{ik}^{k - 1} + d_{k j}^{k - 1})

To find the distance metric, we compute a sequence of metrices

D0, D1, D2, D3 D4

Where matrix D4 is the distance matrix and D0 = W (the weight matrix)

“ $D^{i}$ has the entries which give the distance between every pair of vertices of the graph, where the intermediate node (if any) has a number not higher than $i$ .”

W = D^{0} = 02 \infty 6 \infty 07 \infty 3 \infty 0 \infty \infty \infty 10

W = D^{1} = 02 \infty 6 \infty 07 \infty 3509 \infty \infty 10

W = D^{2} = 0296 \infty 07 \infty 3509 \infty \infty 10

W = D^{3} = 029610071635094610

W = D^{4} = 027610071635094610

The main matrix $D 4$ is the distance matrix, which provides the shortest distance between any pair of vertices.

Note: distance between $v_{i} \to v_{i}$ is zero always.