GESP 七级 · GESP 202403 C++ 七级 第 15 题

下面的程序使用邻接矩阵表达的带权无向图，则从顶点 0 到顶点 3 的最短距离为（ ）。

int weight[4][4] = {
    {0, 2, 5, 8},
    {2, 0, 1, 7},
    {5, 1, 0, 4},
    {8, 7, 4, 0}
};

邻接矩阵是n×n的方阵，matrix[i][j]表示顶点i到j是否有边（有权图存权值）。n个顶点需n²空间。

有向完全图边数为n(n-1)，无向完全图边数为n(n-1)/2。简单图不含自环和重边。

【考点】Dijkstra算法｜邻接矩阵｜带权无向图

2. 🧠 解题思维

看到邻接矩阵就想到最短路径问题。从顶点0出发：直接连3权值8；但0→1（2）+1→2（1）+2→3（4）=7更短。命题人故意把直接边权设成8，诱导你选C，其实最短路径要遍历中间点才能发现更优解。