基于邻接表的Floyd-Warshall算法网格图实现异常排查

嘿，我帮你排查下这个基于邻接表的Floyd-Warshall实现问题，你遇到的所有距离变成INT_MIN类数值的情况，主要是初始化错误和整数溢出导致的，下面是具体问题和修复方案：

核心问题分析 #

• 顶点自距离未正确初始化：Floyd算法要求每个顶点到自身的距离为0，你现在把所有dist[i][j]都设为INT_MAX，这会破坏算法的基础逻辑，导致后续路径计算出现异常。
• 未处理INT_MAX溢出：当dist[i][k]或dist[k][j]是INT_MAX（表示不可达）时，两者相加会触发整数溢出，结果变成负数（接近INT_MIN），错误地触发更新条件，把正常的距离覆盖成无效值。
• 多余的内存分配：代码中current = malloc(sizeof(current));完全没必要，后续current会被指向邻接表的头节点，这行代码会造成内存泄漏。

修正后的代码 #

#include <limits.h>
#include <stdlib.h>

// 假设Graph、EdgeNodePtr等结构体已正确定义
void floyd(Graph *self, int** dist, int** next) { 
    int i, j, k; 
    EdgeNodePtr current; 

    // 初始化距离矩阵和路径矩阵
    for (i = 0; i < self->V; i++) { 
        for (j = 0; j < self->V; j++) { 
            dist[i][j] = INT_MAX; 
            next[i][j] = -1; 
        }
        // 顶点到自身的距离设为0
        dist[i][i] = 0;
        next[i][i] = i;
    } 

    // 填充邻接表中的直接边距离
    for (i = 0; i < self->V; i++) { 
        current = self->edges[i].head; 
        while (current != NULL) { 
            int to = current->edge.to_vertex;
            int weight = current->edge.weight;
            // 只在当前记录的距离更大时更新（避免同顶点多条边的情况）
            if (weight < dist[i][to]) {
                dist[i][to] = weight; 
                next[i][to] = to; 
            }
            current = current->next; 
        } 
    } 

    PRINT // 第一次打印初始状态

    // 标准Floyd-Warshall算法实现，添加溢出检查
    for (k = 0; k < self->V; k++) { 
        for (i = 0; i < self->V; i++) { 
            // 如果i到k不可达，跳过当前循环
            if (dist[i][k] == INT_MAX) continue;
            for (j = 0; j < self->V; j++) { 
                // 如果k到j不可达，跳过当前循环
                if (dist[k][j] == INT_MAX) continue;
                // 检查相加是否会溢出（可选，更严谨）
                if (dist[i][k] > INT_MAX - dist[k][j]) continue;
                // 更新距离和路径
                if (dist[i][j] > dist[i][k] + dist[k][j]) { 
                    dist[i][j] = dist[i][k] + dist[k][j]; 
                    next[i][j] = next[i][k]; 
                } 
            } 
        } 
    } 

    PRINT // 第二次打印最终状态
} 

修复说明 #

1. 新增了dist[i][i] = 0的初始化，符合Floyd算法的基本要求；
2. 在算法核心循环中，先检查dist[i][k]和dist[k][j]是否为INT_MAX，跳过不可达的路径，避免溢出；
3. 额外添加了溢出检查dist[i][k] > INT_MAX - dist[k][j]，进一步防止整数溢出的情况；
4. 删除了多余的malloc语句，避免内存泄漏；
5. 优化了直接边的填充逻辑，处理同顶点多条边的情况（保留最小权重）。

这样修改后，你的距离矩阵就能正确计算出网格图中各顶点之间的最短距离，不会再出现INT_MIN类的无效数值了。

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