Finding All Pairs Shortest Path Using Floyd–Warshall Algorithm

Floyd–Warshall Algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).

Let's say we have 4 nodes and given the 2D array edges containing three values - {from, to, weight} representing a bidirectional and weighted edges between nodes from and to. Supposing we have a distance threshold k and we would like to find out the smallest number of nodes that are reachable through some path whose the distance is at most k.

The pseudocode for Floyd–Warshall algorithm is

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u, v) do
    dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
for each vertex v do
    dist[v][v] ← 0
for k from 1 to |V|
    for i from 1 to |V|
        for j from 1 to |V|
            if dist[i][j] > dist[i][k] + dist[k][j] 
                dist[i][j] ← dist[i][k] + dist[k][j]
            end if

To implement in C++, we first define dist. As dist[i][j] stores the distance between two points, we can initialised the maximum value of k. Let's say the constraint is 1 <= k <= 10^4. We can initialise any values which is greater than 10^4.

vector<vector<int>> dist(n, vector<int>(n, 10005));

Then we need to reset the left diagonal to zero

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

so that we can build the dist[i][j]. Let's say the edge is bidirectional.

for(auto e : edges) dist[e[0]][e[1]] = dist[e[1]][e[0]] = e[2];

Calculate the distance for each pair with Time Complexity: O(n ^ 3)

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

If dist[i][j] is storing a boolean value, we can use

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

Once we got dist[i][j], we can easily find out the answer.

int ans = 0, mi = n;
for(int i = 0; i < n; i++) {
    int cnt = 0;
    for(int j = 0; j < n; j++) {
        cnt += dist[i][j] <= k;
    }
    if(cnt <= mi) {
        mi = cnt;
        ans = i;
    }
}

Here are some practice problems.

• 743. Network Delay Time

• 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

• 1462. Course Schedule IV