题目

某网络中的路由器运行 OSPF 路由协议，下表是路由器 R1 维护的主要链路状态信息（LSI），下图是根据该表的接口名构造出来的网络拓扑。

R1 所维护的 LSI：

	R1 的 LSI	R2 的 LSI	R3 的 LSI	R4 的 LSI	备注
Router ID	10.1.1.1	10.1.1.2	10.1.1.5	10.1.1.6	标识路由器的 IP 地址
Link1 ID	10.1.1.2	10.1.1.1	10.1.1.6	10.1.1.5	所连路由器的 Router ID
Link1 IP	10.1.1.1	10.1.1.2	10.1.1.5	10.1.1.6	Link1 的本地 IP 地址
Link1 Metric	3	3	6	6	Link1 费用
Link2 ID	10.1.1.5	10.1.1.6	10.1.1.1	10.1.1.2	所连路由器的 Router ID
Link2 IP	10.1.1.9	10.1.1.13	10.1.1.10	10.1.1.14	Link2 的本地 IP 地址
Link2 Metric	2	4	2	4	Link2 费用
Net1 Prefix	192.1.1.0/24	192.1.6.0/24	192.1.5.0/24	192.1.7.0/24	直达网络 Net1 的网络前缀
Net1 Metric	1	1	1	1	到达网络 Net1 的费用

说明：每个路由器的"Link1 / Link2"是该路由器自身视角下的两条链路标号，不同路由器的 Link1 不是同一条物理链路。例如 R1 的 Link1 = R1↔R2，R3 的 Link1 = R3↔R4。

R1 构造的网络拓扑（边权为链路费用）：

请回答下列问题：

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

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

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

解析

总思路：题面看似考网络，其实考的是图的抽象 + 邻接表设计 + Dijkstra——把 4 个路由器和 4 个直连子网当作图的顶点，链路当作带权边，问题立刻退化成"加权无向图最短路径"，这是数据结构必修内容。

(1) 网络抽象为哪种结构

答案：图（无向图）。

为什么：

• 图中既有顶点（路由器、子网），也有顶点之间的连接关系（链路）——这是图的标准定义。
• 链路是双向的（A 能到 B，B 也能到 A，且费用相同），所以是无向图。
• 链路有费用（metric），所以是带权图（加权无向图）。

阅卷时只要写出与"图"含义相近的描述（如"网状结构"、"非线性结构"）也可酌情给分，但最规范的回答是加权无向图。

(2) 链式存储结构设计

整体思路：用邻接表存储——每个路由器对应一个表头结点（HNode），其后挂一条单链表，链表中每个结点（LNode）描述该路由器的一条邻接信息（连到哪个路由器 / 直连哪个子网）。

由于 LSI 里有两类邻接信息：

• 连到路由器的链路（Arc）：保存对端 Router ID + 本地 IP + Metric
• 直连的子网（Net）：保存网络前缀 + 子网掩码 + Metric

可以用 union 在同一种 LNode 里表达这两种信息，靠 flag 字段区分。

数据类型定义（C 语言）：

// 描述一条"连到路由器"的链路
typedef struct {
    uint32_t id;        // 所连路由器的 Router ID
    uint32_t ip;        // 该链路本地端的 IP 地址
    int      metric;    // 链路费用
} Arc;

// 描述一个"直连子网"
typedef struct {
    uint32_t prefix;    // 网络前缀（含子网掩码长度也可单独存）
    uint32_t mask;      // 子网掩码
    int      metric;    // 到达子网的费用
} Net;

// 链表结点：表示一条邻接信息（Arc 或 Net）
typedef struct LNode {
    int flag;           // 1: 该结点是 Arc（连到路由器）  2: Net（直连子网）
    union {
        Arc arc;
        Net net;
    } data;
    struct LNode *next; // 链表后继
} LNode;

// 表头结点：每个路由器对应一个
typedef struct HNode {
    uint32_t router_id;     // 该路由器的 Router ID
    LNode   *first;         // 指向该路由器的邻接表头
    struct HNode *next;     // 表头链表的后继（也可改为表头数组）
} HNode;

示意图（仅以 ID 标识结点，省略 IP / Metric 等字段）：

HNode 表头链：
[R1: 10.1.1.1] -> [R2: 10.1.1.2] -> [R3: 10.1.1.5] -> [R4: 10.1.1.6] -> NULL
       |              |                  |                  |
       v              v                  v                  v
   邻接链表        邻接链表            邻接链表           邻接链表

[R1] 邻接链:  Arc(10.1.1.2) -> Arc(10.1.1.5) -> Net(192.1.1.0/24) -> NULL
[R2] 邻接链:  Arc(10.1.1.1) -> Arc(10.1.1.6) -> Net(192.1.6.0/24) -> NULL
[R3] 邻接链:  Arc(10.1.1.6) -> Arc(10.1.1.1) -> Net(192.1.5.0/24) -> NULL
[R4] 邻接链:  Arc(10.1.1.5) -> Arc(10.1.1.2) -> Net(192.1.7.0/24) -> NULL

关键点说明：

1. 表头结点用单链表组织亦可改为定长数组（408 阅卷参考答案两种都给分）。数组实现下 HNode *table[] 索引由 Router ID 哈希得到，查找更快但需要额外哈希函数。
2. 邻接结点用 union 共享存储是为了在一条链表里既能挂"路由器邻接"又能挂"子网邻接"——也可以拆成两条链表（一条专挂 Arc、一条专挂 Net），用两个指针放在表头里，同样给分。
3. 省略的字段：示意图只画 ID（题面要求），实际数据结构里 Arc 还含 IP、Metric，Net 还含 mask、metric。

阅卷时只要给出可行的链式结构且完整保存了 LSI 中的所有信息（Router ID、对端 ID、本地 IP、费用、子网前缀），即给分。union/双指针/分离表均可。

(3) Dijkstra 求 R1 到各子网的最短路径

核心算法：以 R1 为源，逐步把"已确定最短距离"的顶点加入集合 S；每次选 V−S 中距离最小的顶点加入 S，并松弛其邻接边。

初始状态：

顶点	距离	前驱	是否已确定
R1	0	—	✓
N1 (192.1.1.0/24)	∞	—
R2	∞	—
R3	∞	—
R4	∞	—
N2 (192.1.6.0/24)	∞	—
N3 (192.1.5.0/24)	∞	—
N4 (192.1.7.0/24)	∞	—

逐步松弛（每步选当前未确定顶点中距离最小者，加入 S 并松弛邻接边）：

步骤	当前确定	路径	费用	松弛后剩余顶点的距离更新
0	R1	R1	0	N1=1, R2=3, R3=2
1	N1（192.1.1.0/24）	R1→N1	1	（N1 是叶网络，无需松弛）
2	R3	R1→R3	2	N3=3, R4=8
3	R2	R1→R2	3	N2=4, R4=min(8, 3+4)=7（更新）
4	N3（192.1.5.0/24）	R1→R3→N3	3	（叶网络）
5	N2（192.1.6.0/24）	R1→R2→N2	4	（叶网络）
6	R4	R1→R2→R4	7	N4=8
7	N4（192.1.7.0/24）	R1→R2→R4→N4	8	—

按子网代价不减序输出最终答案：

	目的网络	路径	代价（费用）
步骤 1	192.1.1.0/24	直接到达	1
步骤 2	192.1.5.0/24	R1→R3→192.1.5.0/24	3
步骤 3	192.1.6.0/24	R1→R2→192.1.6.0/24	4
步骤 4	192.1.7.0/24	R1→R2→R4→192.1.7.0/24	8

关键点说明：

1. R4 的距离会被更新一次——首先从 R3 端松弛得 8（步骤 2），后来从 R2 端松弛得 7（步骤 3），Dijkstra 取更小者。这是 Dijkstra 能找到全局最短而非贪心局部解的核心机制。
2. 为什么按代价不减序输出——这是 Dijkstra 的天然顺序：每次确定的顶点其最短距离一定不小于上次确定的（前提是无负权边）。题面要求"依次给出"就是要这个顺序。
3. 若考生答案完全正确但顺序与代价不减序不符，可酌情给分（阅卷参考答案的明确说明）。

编者注（生僻术语）：

• OSPF（Open Shortest Path First）= 开放最短路径优先协议，链路状态路由协议族的代表
• LSI（Link State Information）= 链路状态信息，每台 OSPF 路由器维护并向全网广播
• Router ID = 路由器在 OSPF 域内的唯一标识符（一般用接口 IP）

这些是网络层概念，但本题考点完全在数据结构——会做加权无向图的 Dijkstra 即可，OSPF 协议细节不需要懂。