I am applying the all-pairs shortest path algorithm (Floyd-Warshall) to this directed graph:
The graph is represented by its adjacency matrix. The simple code looks like this:
public class ShortestPath {
public static void main(String[] args) {
int x = Integer.MAX_VALUE;
int [][] adj= {
{0, 6, x, 6, 7},
{x, 0, 5, x, x},
{x, x, 0, 9, 3},
{x, x, 9, 0, 7},
{x, 4, x, x, 0}};
int [][] D = adj;
for (int k=0; k<5; k++){
for (int i=0; i<5; i++){
for (int j=0; j<5; j++){
if(D[i][k] != x && D[k][j] != x && D[i][k]+D[k][j] < D[i][j]){
D[i][j] = D[i][k]+D[k][j];
}
}
}
}
//Print out the paths
for (int r=0; r<5; r++) {
for (int c=0; c<5; c++) {
if(D[r][c] == x){
System.out.print("n/a");
}else{
System.out.print(" " + D[r][c]);
}
}
System.out.println(" ");
}
}
}
The above works fine as far as the algorithm is concerned.
I am trying to indicate that a path from any node to itself is not necessarily 0
, as implied by the use of the adjacency matrix here, but can be any possible path through other nodes: For example B -...-...-...-B
Is there a way to modify my current representation to indicate that a shortest path from say, B
to B
, is not zero, but 12
, following the B-C-E-B
route? Can it be done by somehow modifying the adjacency matrix method?
Changing the diagonal elements adjacency matrix from 0 to infinity (theoretically) should work.
It means the self loop cost is infinite and any other path with less than this cost is better hence if a path exists from a node to itself, through other nodes, its cost will be finite and it will replace the infinite value.
Practically you can use maximum value of integer as infinite.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With