GESP 八级 · GESP 202512 C++ 八级 第 5 题

下面是使用邻接矩阵实现的 Dijkstra 算法的核心片段，用于求单源最短路径。在找到当前距离起点最近的顶点 $u$ 后，需要更新其邻接点 $j$ 的距离。横线处应填入的代码是（ ）。

for (int j = 1; j <= n; j++) {
    if (!visited[j] && graph[u][j] < INF) {
        if (________) { // 在此处填入选项
            dis[j] = dis[u] + graph[u][j];
        }
    }
}

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

区分逻辑运算(&&,||,!)和位运算(&,|,~,!)。左移右移注意符号位的处理（算术右移vs逻辑右移）。负数的位运算要小心。

【考点】Dijkstra 算法｜松弛操作｜邻接矩阵遍历

GESP 八级 C++ 必考核心。命题人专门卡住“松弛条件”的理解：Dijkstra 的核心在于不断寻找更短路径，而非单纯遍历。考生若死记“更新距离”却搞反比较方向，必选错。该题不考复杂实现，专测逻辑细节。

此时已选定距离起点最近的未访问点 $u$。遍历其邻接点 $j$ 时，若 $j$ 可达且 $graph[u][j]$ 非无穷，新路径长度即为 $dis[u] + graph[u][j]$。这是 Dijkstra 算法中经典的松弛操作。松弛的本质是“若新路径更短才更新”，故横线需填入 $dis[j] > dis[u] + graph[u][j]$，即当前距离大于新距离时才替换。

B 项正确，直接对应松弛定义。错项全是思维偏差。A 项 $dis[j] < \dots$ 是反向比较，逻辑完全颠倒；C 项 $graph[u][j] > \dots$ 偷换概念，比较的是边权而非路径和；D 项 $dis[j] > graph[u][j]$ 最阴险，它忽略了 $dis[u]$ 的存在，误以为直接边权就是最短距离，这是初学者对 Dijkstra“单源”特性的致命误解。命题人利用学生容易忽略 $dis[u]$ 的非零值特性。

刷到此类题先自问：我到底在判断“新路径是否更短”？记住，Dijkstra 永远只保留更优解。