16. Floyd Warshall
The problem can be found at the following link: Question Link
Problem Description
You are given a weighted directed graph represented by an adjacency matrix dist[][]
of size n x n
, where dist[i][j]
represents the weight of the edge from node i
to node j
. If there is no direct edge, dist[i][j]
is set to a large value (e.g., 10^8
) representing infinity.
The graph may contain negative edge weights, but it does not contain any negative weight cycles.
Your task is to compute the shortest distance between every pair of nodes (i, j)
by modifying the distances in-place.
Note: Sorry for uploading late, my Final Sem exam is going on.
Examples
Example 1:
Output:
[
[0, 4, 5, 5, 7],
[3, 0, 1, 4, 6],
[2, 6, 0, 3, 5],
[3, 7, 1, 0, 2],
[1, 5, 5, 4, 0]
]
Explanation:
Each cell dist[i][j]
in the output shows the shortest distance from node i
to node j
, computed by considering all possible intermediate nodes.
Example 2:
Input:
Output:
[
[0, -1, 2],
[1, 0, 3],
[2, 1, 0]
]
Explanation:
The shortest path from node
2
to node0
is via node1
(i.e.,2 -> 1 -> 0
), which gives a distance of2
.Similarly, the shortest path from node
1
to node2
is1 -> 0 -> 2
, with a total cost of3
.
Constraints:
$(1 \leq \text{dist.size()} \leq 100)$
$(-1000 \leq \text{dist}[i][j] \leq 1000)$
If there is no edge between two nodes, the weight is given as a large value (e.g.,
10^8
) representing infinity.
My Approach
Floyd Warshall
Concept:
The algorithm considers every node as an intermediate vertex and updates the distance between every pair of nodes (i, j) if including an intermediate node ( k ) yields a smaller path.
Algorithm Steps:
For every intermediate node
k
from0
ton-1
:For each source node
i
from0
ton-1
:For each destination node
j
from0
ton-1
:If the path from
i
toj
can be minimized by passing throughk
(i.e., ifd[i][j] > d[i][k] + d[k][j]
), then updated[i][j]
.
Time and Auxiliary Space Complexity
Expected Time Complexity: O(nΒ³), due to the triple nested loop over ( n ) nodes.
Expected Auxiliary Space Complexity: O(1), as we update the matrix in-place and only use a few additional variables.
Code (C++)
class Solution {
public:
void floydWarshall(vector<vector<int>> &d) {
int n = d.size(), inf = 1e8;
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (d[i][k] < inf && d[k][j] < inf && d[i][j] > d[i][k] + d[k][j])
d[i][j] = d[i][k] + d[k][j];
}
};
Code (Java)
class Solution {
public void floydWarshall(int[][] d) {
int n = d.length, inf = 100000000;
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (d[i][k] < inf && d[k][j] < inf && d[i][j] > d[i][k] + d[k][j])
d[i][j] = d[i][k] + d[k][j];
}
}
Code (Python)
class Solution:
def floydWarshall(self, d):
n, inf = len(d), 100000000
for k in range(n):
for i in range(n):
for j in range(n):
if d[i][k] < inf and d[k][j] < inf and d[i][j] > d[i][k] + d[k][j]:
d[i][j] = d[i][k] + d[k][j]
Contribution and Support:
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Letβs make this learning journey more collaborative!
β If you find this helpful, please give this repository a star! β
πVisitor Count
Last updated