All Pairs Shortest Path (Floyd-Warshall Algorithm)

Introduction

For a given connected weighted graph , 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}=\begin{cases}c_{ij}, & \text{if vertex }i\text{ is adjacent to }j\\ \infty, & \text{otherwise}\end{cases}

Where:

= weight of edge

Distance Matrices

The algorithm computes a series of matrices:

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

Here:

stores the shortest path distances between every pair
Intermediate vertices allowed must be numbered ≤ k

So,

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

Recursive Relation

Each entry in matrix is computed using values from :

d_{ij}^{k}=\min\left\{d_{ij}^{k-1},\;d_{ik}^{k-1}+d_{kj}^{k-1}\right\}

Interpretation:

First value: shortest path from without using vertex
Second value: shortest path from using vertex
We pick the shorter one.

Meaning

For step , we check whether including vertex as an intermediate point gives a shorter route between every pair . 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 since there are three nested loop each with an iteration

For the given problem, the number of nodes is:

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

W=D^0=\left[\begin{matrix}0 & \infty & 3 & \infty\\ 2 & 0 & \infty & \infty\\ \infty & 7 & 0 & 1\\ 6 & \infty & \infty & 0\end{matrix}\right]

Recursive Relation

To compute from :

d_{ij}^{k}=\min\left(d_{ij}^{k-1},\;d_{ik}^{k-1}+d_{kj}^{k-1}\right)

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)

“ 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 .”

W=D^0=\left[\begin{matrix}0 & \infty & 3 & \infty\\ 2 & 0 & \infty & \infty\\ \infty & 7 & 0 & 1\\ 6 & \infty & \infty & 0\end{matrix}\right]

W=D^1=\left[\begin{matrix}0 & \infty & 3 & \infty\\ 2 & 0 & 5 & \infty\\ \infty & 7 & 0 & 1\\ 6 & \infty & 9 & 0\end{matrix}\right]

W=D^2=\left[\begin{matrix}0 & \infty & 3 & \infty\\ 2 & 0 & 5 & \infty\\ 9 & 7 & 0 & 1\\ 6 & \infty & 9 & 0\end{matrix}\right]

W=D^3=\left[\begin{matrix}0 & 10 & 3 & 4\\ 2 & 0 & 5 & 6\\ 9 & 7 & 0 & 1\\ 6 & 16 & 9 & 0\end{matrix}\right]

W=D^4=\left[\begin{matrix}0 & 10 & 3 & 4\\ 2 & 0 & 5 & 6\\ 7 & 7 & 0 & 1\\ 6 & 16 & 9 & 0\end{matrix}\right]

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

Note: distance between is zero always.