🏷️ 知识点：最短路径

对如下有向图带权图，若采用迪杰斯特拉（Dijkstra）算法求从源点 a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余最短路径的目标顶点依次是（ ）。

最短路径

A. d, e, f

B. e, d, f

C. f, d, e

D. f, e, d

[tag_link]

正确答案：C

从 a 到各顶点的最短路径的求解过程：

后续目标顶点依次为 f,d,e。第三轮已有 dist(f)=4<dist(d)=5<dist(e)=7，先固定 f；随后固定 d，并把 e 更新为路径 a→b→d→e、长度 6；最后固定 e。因此选 C。

使用迪杰斯特拉（Dijkstra）算法求下图中从顶点 1 到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是（ ）。

最短路径

A. 5, 2, 3, 4, 6 B. 5, 2, 3, 6, 4 C. 5, 2, 4, 3, 6 D. 5, 2, 6, 3, 4

[tag_link]

正确答案：B

根据 Dijkstra 算法，从顶点 1 到其余各顶点的最短路径如下表所示。

顶点 1 到其余顶点的最终最短距离分别为 d(5)=4、d(2)=5、d(3)=7、d(6)=9、d(4)=11。Dijkstra 每轮固定当前暂定距离最小的未确定顶点，因此顺序为 5,2,3,6,4，选 B。

使用 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。

( 1 0 分 )带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目 标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：

① 设最短路径初始时仅包含初始顶点，令当前顶点u 为初始顶点；

②选择离u 最近且尚未在最短路径中的一个顶点v, 加入到最短路径中，修改当前顶点u=v;

③重复步骤②,直到u 是目标顶点时为止。

请问上述方法能否求得最短路径?若该方法可行，请证明之；否则，请举例说明。

[tag_link]

图 (1) 中，设初始顶点为 1，目标顶点为 4，欲求从顶点 1 到顶点 4 之间的最短路径，显然这两点之间的最短路径长度为 2。利用给定方法求得的路径长度为 3，但这条路径并不是这两点之间的最短路径。 图 (2) 中，设初始顶点为 1，目标顶点为 3，欲求从顶点 1 到顶点 3 之间的最短路径。利用给定的方法，无法求出顶点 1 到顶点 3 的路径。

【评分说明】①若考生回答“能求得最短路径”，无论给出何种证明，均不给分。②考生只要举出类似上述的一个反例说明“不能求得最短路径”或答案中体现了“局部最优不等于全局最优”的思想，均可给 6 分；若举例说明不完全正确，可酌情给分。

(15分)某网络中的路由器运行OSPF路由协议，题42表是路由器R1维护的主要链路状态信息(LSI), 题42图是根据题42表的接口名构造出来的网络拓扑。

请回答下列问题。

(1)本题中的网络可抽象为数据结构中的哪种结构?

(2)针对题42表中的内容，设计合理的链式存储结构，以保存题42表中的链路状态信息( LSI) 。 要求给 出链式存储结构的数据定义，并画出对应题42表的链式存储结构示意图(示意图中仅以ID 标识结点)。

(3)按照迪杰斯特拉( Dijkstra) 算法的策略，依次给出R1 到达题42图中子网192.1.x.x的最短路径及费 用。

题42表R1所维护的LSI

[tag_link]

很多考生乍看之下以为是网络的题目，其实该题本身并没有涉及太多的网络知识点，只是 应用了网络的模型，实际上考查的还是数据结构的内容。 1）图（1 分） 题中给出的是一个简单的网络拓扑图，可以抽象为无向图。 【评分说明】只要考生的答案中给出与图含义相似的描述，例如，“网状结构”“非线性结构”等，同样 给分。 2）链式存储结构的如下图所示。

struct Arc {
    uint32_t id;
    uint32_t ip;
    int metric;
};

struct Net {
    uint32_t prefix;
    uint32_t mask;
    int metric;
};

struct LNode {
    LNode *next;           // flag == 1：链路连接到路由器
                           // flag == 2：链路连接到子网
    int flag;
    union NetOrArc {
        Net net;
        Arc arc;
    };
};

struct HNode {
    uint32_t router_id;
    LNode *next;
    HNode *next_hnode;
};

【评分说明】① 若考生给出的答案是将链表中的表头结点保存在一个一维数组中（即采用邻接表形式），同样给分。② 若考生给出的答案中，弧结点没有使用 union 定义，而是采用两种不同的结构分别表示 Link 和 Net，同时在表头结点中定义了两个指针，分别指向由这两种类型的结点构成的两个链表，同样给分。③ 考生所给答案的弧结点中，可以在单独定义的域中保存各直连网络 IP 地址的前缀长度，也可以与网络地址保存在同一个域中。④ ③的标准给分。⑤ 若考生给出的答案中，图示部分与其数据类型定义部分一致，图示只要能够体现链式存储结构和网络连接关系（可以不给出结点内细节信息），即可给分。⑥ ①

下列关于图的最短路径的叙述中，正确的是（　　）。

A. 最短路径一定是简单路径 B. Dijkstra 算法不适合求有回路的带权图的最短路径 C. Dijkstra 算法不适合求任意两个顶点的最短路径 D. Dijkstra 算法可以正确处理含有负权边的图

[tag_link]

正确答案：A

结论

选 A。

推导

在不存在负权回路的通常最短路定义下，若一条路径重复顶点，就含有回路；去掉该回路不会增加长度，因此存在一条同样不长于它的简单最短路径。Dijkstra 可处理有回路图，也可从每个源点重复运行求任意点对最短路，但要求边权非负，故 B、C、D 均错误。

易错点

Dijkstra 的限制是“不能有负权边”，不是“不能有回路”。

下列关于图的最短路径的叙述中，正确的是（　　）。

Ⅰ．Dijkstra 算法求单源最短路径不允许边的权为负。 Ⅱ．Dijkstra 算法求每对顶点间的最短路径的时间复杂度为 O(n²)。 Ⅲ．Floyd 算法求每对顶点间的最短路径允许边权为负，但不允许含有负权回路。

A. Ⅰ、Ⅱ和Ⅲ B. 仅Ⅰ C. Ⅰ和Ⅲ D. Ⅱ和Ⅲ

[tag_link]

正确答案：C

结论

选 C。

推导

Ⅰ正确：Dijkstra 的贪心确定性要求边权非负。Ⅱ错误：对 n 个源点分别运行 Dijkstra（朴素实现）为 O(n³)，不是 O(n²)。Ⅲ正确：Floyd 可处理负边，但负权回路使最短路无定义。

易错点

要区分“单源”与“每对顶点”；算法调用次数会改变复杂度。

用 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 的顶点。