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](https://leetcode.com/problems/network-delay-time/) - [1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance](https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/) - [1462. Course Schedule IV](https://leetcode.com/problems/course-schedule-iv/)