NOIP 提高组初赛 · NOIP 2015 提高组初赛试题 第 28 题

（最短路径问题）无向连通图 $G$ 有 $n$ 个结点，依次编号为 $0,1,2,\dots,(n-1)$。用邻接矩阵的形式给出每条边的边长，要求输出以结点 $0$ 为起点出发，到各结点的最短路径长度。

使用 Dijkstra 算法解决该问题：利用 dist 数组记录当前各结点与起点的已找到的最短路径长度；每次从未扩展的结点中选取 dist 值最小的结点 $v$ 进行扩展，更新与 $v$ 相邻的结点的 dist 值；不断进行上述操作直至所有结点均被扩展，此时 dist 数据中记录的值即为各结点与起点的最短路径长度。（第五空 $2$ 分，其余 $3$ 分）

#include <iostream> 
using namespace std; 
const int MAXV = 100; 
int n, i, j, v; int w[MAXV][MAXV]; // 邻接矩阵，记录边长 // 其中 w[i][j]为连接结点 i 和结点 j 的无向边长度，若无边则为-1 
int dist[MAXV]; int used[MAXV]; // 记录结点是否已扩展（0：未扩展；1：已扩展） 
int main() 
{ 
    cin >> n; 
    for (i = 0; i < n; i++) 
        for (j = 0; j < n; j++) 
            cin >> w[i][j]; 
dist[0] = 0;
for (i = 1; i < n; i++) 
        dist[i] = -1; 
    for (i = 0; i < n; i++) 
        used[i] = 0; 
    while (true) { 
            (1)    ; 
        for (i = 0; i < n; i++) 
            if (used[i] != 1 && dist[i] != -1 && (v == -1 ||     (2)    )) 
    

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考的是Dijkstra算法在邻接矩阵下的具体实现细节。拿到题先别急着填，心里过一遍算法流程：初始化距离、循环找最小未扩展点、标记、松弛。关键就是那句‘从未扩展结点中选取dist最小’怎么翻译成代码里的比较逻辑，以及松弛时如何判断更新。

最容易栽跟头的地方有两个：一是把used数组理解成‘访问过’，其实它只标记‘已扩展’，一旦扩展，dist就锁死了，不能再更新，很多人会误以为可以反复优化。二是松弛条件的写法，题目给的选项里常把dist[v]+w[v][i]和dist[i]的大小关系写反，或者漏掉dist[i]==-1（代表无穷大）的情况。还有，找最小点v时，如果v初始化为-1，比较逻辑里必须处理v==-1的情况，否则第一遍循环会出错。

考点与概念

这道题考查的是单源最短路径的经典算法——Dijkstra算法。核心思想很简单：从起点开始，每次挑一个还没确定最短距离的节点里，距离起点最近的那个，把它‘定死’（标记为已扩展），然后用它去更新它所有邻居的距离。这里有个硬性前提：图中不能有负权边，否则贪心策略会失效。题目里用的是邻接矩阵存图，w[i][j]就是i到j的边长，-1代表没边。

命题人怎么挖坑

命题人最喜欢在‘找最小’和‘松弛’这两个环节动手脚。

第一，找最小的时候，代码里有个变量v用来存当前找到的最小距离节点的编号。初始化时v必须是-1（表示还没找到）。然后在循环里遍历所有节点，如果节点没被扩展过（used[i]!=1）且有距离（dist[i]!=-1），就要比较dist[i]和dist[v]。这里有个逻辑陷阱：当v还是-1时，任何合法的dist[i]都比它小，所以条件里必须显式判断v==-1，或者利用dist[v]在v==-1时是个极大值（比如-1本身如果代表无穷大，那比较逻辑要反过来）。题目给的选项里，dist[i] < dist[v]或者dist[v] > dist[i]都是对的，因为它们本质是一回事，只是写法不同。很多人会写成dist[i] <= dist[v]，这在v刚被赋值为某个节点时没问题，但如果v还是-1，dist[-1]是非法访问，所以必须避开等号或者确保v不为-1。

第二，松弛的时候，更新邻居i的距离。只有当w[v][i]存在（不等于-1），并且dist[i]可以变得更小的时候才更新。这里有两个更新条件：要么dist[i]原本是-1（无穷大），要么dist[v] + w[v][i]比当前的dist[i]小。命题人常把这两个条件拆开，或者把大小关系写反，比如写成dist[i] > dist[v] + w[v][i]，这其实也是对的，只是表述角度不同。还有的同学会漏掉dist[i] == -1的判断，导致第一次遇到某个节点时无法更新。