PROBLEM DESCRIPTION
The problem is to find the shortest distances between every pair of vertices in a given edge-weighted directed graph. The graph is represented as an adjacency matrix of size nxn. Matrix[i][j] denotes the weight of the edge from i to j. If Matrix[i][j]=-1, it means there is no edge from i to j.
Note : Modify the distances for every pair in-place.
SOLUTION
Good Explanation by takeUForward
1
2
3
4
5
6
7
8
Consider intermediate nodes from [0,n]
Consider pair wise for nodes:
i -> [0, n]
j -> [0, n]
Keep updating min distance between
i->j directly
OR
i->k then k->j.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution
{
private static final int MAX = 1001;
public void shortest_distance(int[][] matrix)
{
int n = matrix.length;
// Replace all -1s in the matrix with MAX to represent no direct path between nodes.
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
// Use MAX as a substitute for infinity.
if(matrix[i][j] == -1)
matrix[i][j] = MAX;
}
}
// Iterate over all pairs of nodes (i, j) and try to find a shorter path from i to j via an intermediate node k.
for(int k = 0; k < n; k++){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
// Update the distance from i to j by considering the distance from i to k
// plus the distance from k to j, and take the minimum.
matrix[i][j] = Math.min(matrix[i][j], matrix[i][k] + matrix[k][j]);
}
}
}
// Convert all MAX values back to -1 to indicate no path between nodes.
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(matrix[i][j] >= MAX)
matrix[i][j] = -1;
}
}
}
}