权重邻接矩阵生成错误，求问题原因及解决方法

问题描述 #

需要生成权重邻接矩阵用于最短权重路径计算，但当前生成结果不符合预期：矩阵对角线需全为0，相邻顶点对应位置应为边的权重，但实际输出不满足要求。以下是边定义代码与错误的邻接矩阵生成代码：

边定义代码 #

//set the source and destination of each edge
g->edge[0]->src = 0;
g->edge[0]->dest = 1;
g->edge[0]->weight = 9;

g->edge[1]->src = 0;
g->edge[1]->dest = 10;
g->edge[1]->weight = 6;

g->edge[2]->src = 1;
g->edge[2]->dest = 2;
g->edge[2]->weight = 3;

g->edge[3]->src = 1;
g->edge[3]->dest = 10;
g->edge[3]->weight = 2;

g->edge[4]->src = 2;
g->edge[4]->dest = 3;
g->edge[4]->weight = 2;

g->edge[5]->src = 2;
g->edge[5]->dest = 6;
g->edge[5]->weight = 3;

g->edge[6]->src = 2;
g->edge[6]->dest = 5;
g->edge[6]->weight = 3;

g->edge[7]->src = 3;
g->edge[7]->dest = 4;
g->edge[7]->weight = 5;

g->edge[8]->src = 4;
g->edge[8]->dest = 5;
g->edge[8]->weight = 4;

g->edge[9]->src = 6;
g->edge[9]->dest = 10;
g->edge[9]->weight = 2;

g->edge[10]->src = 6;
g->edge[10]->dest = 7;
g->edge[10]->weight = 9;

g->edge[11]->src = 7;
g->edge[11]->dest = 8;
g->edge[11]->weight = 7;

g->edge[12]->src = 7;
g->edge[12]->dest = 9;
g->edge[12]->weight = 2;

g->edge[13]->src = 8;
g->edge[13]->dest = 9;
g->edge[13]->weight = 7;

g->edge[14]->src = 9;
g->edge[14]->dest = 10;
g->edge[14]->weight = 5;

错误的邻接矩阵生成代码 #

for (i = 0; i < numberOfVertices; i++)
{
    adjacency_matrix[i][i] = 0;
    for (j = i + 1; j < numberOfVertices; j++)
    {
            adjacency_matrix[i][j] = g->edge[i]->weight;
            adjacency_matrix[j][i] = g->edge[i]->weight;
    }
}

代码问题分析 #

这段生成代码存在两个核心错误：

• 逻辑匹配错误：代码直接用顶点索引i去取g->edge[i]的权重，强制给所有i<j的顶点对赋值，但实际只有部分顶点对存在边，大部分顶点对是无连接的，应该设为无穷大（或表示无连接的特殊值）。
• 数组越界风险：边的数量是15条，但顶点数是11个（编号0-10），当i>=15时，g->edge[i]会访问超出数组范围的内存，导致未定义行为。

修正后的代码 #

正确的做法是先初始化矩阵所有元素为无穷大（表示无连接），再设置对角线为0，最后遍历所有边，根据每条边的src和dest设置对应位置的权重：

#include <limits.h> // 引入INT_MAX定义

// 初始化邻接矩阵：所有元素设为无穷大，对角线设为0
for (i = 0; i < numberOfVertices; i++)
{
    for (j = 0; j < numberOfVertices; j++)
    {
        adjacency_matrix[i][j] = INT_MAX;
    }
    adjacency_matrix[i][i] = 0;
}

// 遍历所有边，填充邻接矩阵
int numberOfEdges = 15; // 或者从图结构中获取边数
for (i = 0; i < numberOfEdges; i++)
{
    int src = g->edge[i]->src;
    int dest = g->edge[i]->dest;
    int weight = g->edge[i]->weight;
    // 无向图，双向赋值
    adjacency_matrix[src][dest] = weight;
    adjacency_matrix[dest][src] = weight;
}

这样生成的邻接矩阵会符合预期：对角线全为0，存在边的顶点对对应位置为边的权重，无连接的顶点对为无穷大，可直接用于Dijkstra、Floyd-Warshall等最短路径算法。

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