我为一个100x 100邻接矩阵编写了代码,它表示以下有向图:
我试图使用floyd warshall算法来找到图中所有蓝色节点对的最短路径。如何只找到选定节点的所有对最短路径这是我到目前为止写的代码:
public class AdjacencyMatrix
{
public static final int NUM_NODES = 100;
public static final int INF = Integer.MAX_VALUE;
public static boolean even(int num)
{
return num%2==0;
}
public static boolean odd(int num)
{
return num%2==1;
}
public static void initialize(int [][] adjMat, int N)
{
for(int i = 0; i < N; i++)
for(int j = 0; j <N; j++)
adjMat[i][j]=INF;
for(int x = 0; x<N; x++)
{
int row = x/10;
int column = x%10;
if (even(row)) {
if (column!=9)
adjMat[x][x+1]=1;
}
if (odd(row)) {
if (column!=0)
adjMat[x][x-1]=1;
}
if (even(column)){
if (row!=9)
adjMat[x][x+10]=1;
}
if (odd(column)) {
if (row!=0)
adjMat[x][x-10]=1;
}
}
}
public void floydWarshall(int[][] adjMat, int N)
{
adjMat = new int[N][N];
initialize(adjMat, NUM_NODES);
for(int k = 0; k < N; ++k) {
for(int i = 0; i < N; ++i) {
for(int j = 0; j < N; ++j) {
adjMat[i][j] = Math.min(adjMat[i][j], adjMat[i][k] + adjMat[k][j]);
}
}
}
}
public static void main(String[] args)
{
int adjMat[][] = new int[NUM_NODES][NUM_NODES];
initialize(adjMat, NUM_NODES);
int A,B,C,D,E,F,G,H,I,W;
A = 20;
B = 18;
C = 47;
D = 44;
E = 53;
F = 67;
G = 95;
H = 93;
I = 88;
W = 66;
System.out.println(adjMat[A][B]);
System.out.println();
}
}
最佳答案
首先,不应该给FuySythHyLar()中的AdjMad参数分配新的值,因为在退出该方法后,该值不会被保存。
下一步是检查adjmat[i][k]和adjmat[k][j]是否等于inf,如果是,则继续循环:
for(int k = 0; k < N; ++k) {
for(int i = 0; i < N; ++i) {
for(int j = 0; j < N; ++j) {
if (adjMat[i][k] != INF && adjMat[k][j] != INF) {
adjMat[i][j] = Math.min(adjMat[i][j], adjMat[i][k] + adjMat[k][j]);
}