🏷️ 知识点：松弛操作

用 Dijkstra 算法求带权有向图从顶点 0 出发的最短路径。在算法执行的某时刻，已求得最短路径的顶点集合 S={0,2,3,4}，下一步选取的目标顶点是 1，则可能被修改的最短路径是（　　）。

A. 从顶点 0 到顶点 3 的最短路径 B. 从顶点 0 到顶点 2 的最短路径 C. 从顶点 2 到顶点 4 的最短路径 D. 从顶点 0 到顶点 1 的最短路径

[tag_link]

正确答案：D

结论

选 D。

推导

集合 S 中顶点的源点最短距离已经确定，之后的松弛只会检查从新确定的顶点到 V−S 的边。因此不可能改变 0→3、0→2 或 2→4 这类已确定路径；只能把尚未确定的 0→1 的暂定距离更新为更短值（权威表述为“只能修改从源点 0 到集合 V−S 中顶点的路径”）。

易错点

“选出顶点 1”表示其路径被最终确定；被松弛修改的是选出前的暂定值，不能回改已加入 S 的顶点。