🏷️ 知识点：Dijkstra 算法

使用 Dijkstra 算法求下图中从顶点 1 到其余各顶点的最短路径，将当前找到的从顶点 1 到顶点 2、3、4、5 的最短路径长度保存在数组 dist 中，求出第二条最短路径后，dist 中的内容更新为（ ）。

最短路径

A. 26, 3, 14, 6 B. 25, 3, 14, 6 C. 21, 3, 14, 6 D. 15, 3, 14, 6

[tag_link]

正确答案：C

初始 dist=(26,3,∞,6)（下标顺序为顶点 2、3、4、5）。Dijkstra 算法先固定顶点 3，并用边 3→2(22) 将顶点 2 更新为 3+22=25，得到 (25,3,∞,6)；再固定顶点 5，用 5→4(8) 得 14，并用 5→2(15) 得 21，故第二次固定后为 dist=(21,3,14,6)，选 C。