Java中基于Floyd-Warshall算法的介数中心性计算错误排查

我帮你梳理了代码里的几个核心问题，这些应该就是导致结果不符合预期的原因：

1. 初始化阶段的错误：未处理自身节点的情况 #

在无向无权图中，一个节点到自身的最短距离应该是0，路径就是它自己。但你的代码里，当i == j时，因为adjMatrix[i][j] == 0，会被设置为distance[i][j] = noPath，R[i][j] = -5000，这完全不符合逻辑。而且后续统计时还会把这种无效路径算入计数，导致节点自身的计数虚高。

修正初始化代码：

for (int i = 0; i < numVertices; i++) {
    for (int j = 0; j < numVertices; j++) {
        if (i == j) {
            distances[i][j] = 0;
            R[i][j] = i; // 自身到自身的前驱是自己
        } else if (adjMatrix[i][j] == 0) {
            distances[i][j] = noPath;
            R[i][j] = -5000;
        } else {
            distances[i][j] = adjMatrix[i][j];
            R[i][j] = j;
        }
    }
}

2. Floyd-Warshall未处理多条最短路径的情况 #

你的代码只在发现更短路径时更新R数组，但当存在多条等长的最短路径时，当前逻辑只会记录其中一条，导致后续统计的路径数严重缺失——这是介数计算错误的核心原因，因为介数需要统计所有最短路径，而非单条。

要解决这个问题，你需要额外维护一个pathCount数组，记录每个i->j的最短路径总数，同时在发现等长路径时更新计数：

添加路径计数的Floyd-Warshall修正：

// 新增路径计数数组
int[][] pathCount = new int[numVertices][numVertices];
// 初始化计数
for (int i = 0; i < numVertices; i++) {
    for (int j = 0; j < numVertices; j++) {
        if (i == j) {
            pathCount[i][j] = 1;
        } else if (adjMatrix[i][j] != 0) {
            pathCount[i][j] = 1;
        } else {
            pathCount[i][j] = 0;
        }
    }
}

// 修改Floyd-Warshall循环
for (int k = 0; k < numVertices; k++) {
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            if (distances[i][k] != noPath && distances[k][j] != noPath) {
                if (distances[i][j] > distances[i][k] + distances[k][j]) {
                    // 发现更短路径，更新距离、前驱和计数
                    distances[i][j] = distances[i][k] + distances[k][j];
                    R[i][j] = R[i][k];
                    pathCount[i][j] = pathCount[i][k] * pathCount[k][j];
                } else if (distances[i][j] == distances[i][k] + distances[k][j] && k != j) {
                    // 发现等长的最短路径，累加计数
                    pathCount[i][j] += pathCount[i][k] * pathCount[k][j];
                }
            }
        }
    }
}

3. 统计阶段包含了无效的i==j路径 #

介数中心性的定义是：统计所有不同节点对(s,t)（s≠t）的最短路径中，经过目标节点v的次数。你的代码遍历了所有i和j，包括i==j的情况，这会把每个节点自身的无效路径算入计数，导致结果偏差。

修正统计循环：

HashMap<Integer, Integer> frequencies = new HashMap<>();
for (int i = 0; i < numVertices; i++) {
    for (int j = 0; j < numVertices; j++) {
        if (i == j || distances[i][j] == noPath) {
            continue; // 跳过自身节点和不可达的情况
        }
        // 统计所有最短路径中经过的节点
        countNodesInAllShortestPaths(i, j, pathCount, distances, frequencies);
    }
}

4. 单路径枚举无法覆盖所有最短路径 #

你的findShortestPath方法只能找到一条最短路径，但介数需要统计所有最短路径中节点的出现次数。你需要实现一个递归方法来遍历所有可能的最短路径，结合pathCount数组来统计次数：

新增统计所有路径节点的方法：

private void countNodesInAllShortestPaths(int s, int t, int[][] pathCount, int[][] distances, HashMap<Integer, Integer> frequencies) {
    if (s == t) return;
    // 累加当前节点的出现次数：s到t的所有路径都会经过s，所以加pathCount[s][t]次
    frequencies.put(s, frequencies.getOrDefault(s, 0) + pathCount[s][t]);
    // 遍历所有可能的中间节点k
    for (int k = 0; k < numVertices; k++) {
        if (k == s || distances[s][k] + distances[k][t] != distances[s][t]) {
            continue;
        }
        // 递归统计k到t的路径中的节点
        countNodesInAllShortestPaths(k, t, pathCount, distances, frequencies);
    }
}

最后：修正输出逻辑 #

你的输出代码里，先把索引映射到实际节点值，但最后打印的还是frequencies的key（索引），而不是temp里的实际节点值，这也会导致你看到的节点ID不对：

修正输出：

// 替换原来的输出逻辑
System.out.println("Top 5 nodes: \nNode - Count");
temp.entrySet().stream()
    .sorted(Map.Entry.comparingByValue(Collections.reverseOrder()))
    .limit(5)
    .forEach((node, frequency) -> System.out.println(node + " - " + frequency));

通过以上修正，应该就能得到正确的介数中心性结果，让节点50393960回到第一的位置。

内容的提问来源于stack exchange，提问作者user2764359