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

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

int weight[4][4] = {
    { 0,  1,  7, 100},
    { 1,  0,  5,  15},
    { 7,  5,  0,   6},
    {100, 15,  6,   0}};

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

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

【考点】最短路径算法｜邻接矩阵｜Dijkstra/Floyd

🎯 考纲定位 GESP 八级图与树专项，必考最短路径。命题人卡住的是"只会看直接边"的考生——他们看到 0→3 的 100 就慌了，完全没意识到中间节点能绕路。

🧠 解题思维 从 0 出发：

• 直接到 3：100
• 0→1→3：1+15=16
• 0→1→2→3：1+5+6=12
• 0→2→3：7+6=13

枚举所有路径，12 最小。小图可手推，大图用 Dijkstra 或 Floyd。

🪤 陷阱拆解

• A 项 100：只盯着 0→3 这条边，没考虑绕路
• B 项 16：只想到 0→1→3，漏了经过 2 的更短路径
• D 项 13：路径 0→2→3 确实存在，但比 12 长

最阴险的是 D——它用的是真实存在的两条边相加，考生若只验证"路径是否存在"就会误选。记住：最短路径不是"任意路径"，而是"所有路径里最小的"。

🔄 反命题思维 若改成有向图，0→2 反向不存在，D 项 13 的路径就断了，答案可能变成 B 或 100。若允许负权边，Dijkstra 失效，需 Bellman-Ford。刷到此类题先问自己：图是否有向？边权是否非负？无向非负才放心用 Dijkstra。