408 > 计算机网络 > 路由算法：链路状态路由

一、定位信息

所属圈层：核心层
前置知识：需了解图论中Dijkstra最短路径算法的基本思想，以及链路代价、邻居发现等基本路由概念
知识网络位置：链路状态路由是与距离-向量路由并列的另一大类路由算法，是理解OSPF协议的直接基础。与CN-04-01形成对比关系，共同构成路由算法的两大范式
考点热度等级：H级（高频重点） — 链路状态路由与距离-向量路由的对比几乎每年都会涉及

二、知识点讲解

2.1 基本概念

链路状态路由（Link-State Routing，LS）的核心思想是：每个路由器获取全网拓扑信息，然后独立计算到达每个目的网络的最短路径。与距离-向量路由"只听邻居"不同，链路状态路由要求每个路由器构建出完整的网络拓扑图，再用Dijkstra算法求最短路径。

2.2 工作过程

链路状态路由的工作分为以下五个阶段：

阶段一：邻居发现 每个路由器通过发送Hello分组发现直连邻居，并测量到邻居的链路代价。

阶段二：构建链路状态分组（LSP/LSA） 每个路由器创建一个链路状态分组（Link-State Packet），包含：

发送方标识（路由器ID）
序列号（用于区分新旧分组）
生存时间（TTL，防止过期分组在网络中滞留）
所有邻居列表及对应链路代价

阶段三：泛洪（Flooding） 每个路由器将LSP发送给所有邻居（除收到该分组的接口外），邻居收到后再转发给它们的邻居，以此类推，直到全网所有路由器都收到该LSP。这是LS与DV的关键区别之一——LS使用泛洪而非周期性广播。

阶段四：构建完整拓扑图 每个路由器收集到所有其他路由器的LSP后，构建出完整的网络拓扑图（以图的形式存储）。

阶段五：Dijkstra算法计算最短路径 每个路由器以自身为源节点，对拓扑图运行Dijkstra算法，计算到所有目的网络的最短路径，生成路由表。

2.3 Dijkstra算法简述

设 $S$ 为已确定最短路径的节点集合， $d(v)$ 为从源节点到 $v$ 的当前最短距离， $w(u,v)$ 为边 $(u,v)$ 的代价：

初始化： $S = \{源节点\}$ ， $d(源) = 0$ ，其余 $d(v) = \infty$
从不在 $S$ 中的节点中选择 $d(v)$ 最小的节点 $u$ ，加入 $S$
对 $u$ 的所有邻居 $v$ ，若 $d(u) + w(u,v) < d(v)$ ，则更新 $d(v) = d(u) + w(u,v)$
重复步骤2-3，直到所有节点都在 $S$ 中

2.4 LS与DV的详细对比

对比维度	距离-向量（DV）	链路状态（LS）
信息获取方式	只接收邻居的路由表	泛洪获取全网LSP
全局视图	无，只知道邻居视角	有，每个路由器都有全网拓扑图
计算算法	Bellman-Ford	Dijkstra
更新方式	周期性全量更新	仅在链路变化时泛洪LSP
收敛速度	慢	快
消息量	每次发送完整路由表	仅泛洪变化的LSP
路由环路	容易出现	不易出现
计算开销	低	高（需要运行Dijkstra）
内存开销	低（只存路由表）	高（需存全网拓扑图）
代表协议	RIP	OSPF

2.5 LS的优缺点

优点：每个路由器有全局视图，不会出现路由环路；收敛速度快；泛洪机制保证信息可靠传播
缺点：每个路由器需要存储全网拓扑，内存开销大；Dijkstra算法计算复杂度为 $O(n^2)$ ；泛洪可能在大型网络中造成较大带宽消耗

三、记忆与理解辅助

口诀："链路状态泛洪传，全局拓扑建完全；Dijkstra求最短，OSPF用的就是它。"
类比记忆：链路状态路由就像"每个人手里都有一张完整的地图"——通过泛洪机制收集全网信息，然后自己在地图上找最短路。而距离-向量路由是"只听邻居指路"。
对比表格速记（核心差异5条必须记住）：
- LS用泛洪，DV用周期广播
- LS有全局视图，DV只看邻居
- LS用Dijkstra，DV用Bellman-Ford
- LS收敛快，DV收敛慢
- LS代表OSPF，DV代表RIP
数字记忆：Dijkstra算法时间复杂度 $O(n^2)$ （朴素实现），其中 $n$ 为节点数

四、例题与精解

例题1（基础巩固）

题目：以下关于链路状态路由算法的描述中，正确的是（） A. 每个路由器将自己的完整路由表泛洪给所有邻居 B. 每个路由器只接收邻居路由器的链路状态信息 C. 每个路由器接收全网的链路状态信息，独立计算最短路径 D. 每个路由器根据邻居的路由表更新自己的路由表

命题意图：考查对链路状态路由与距离-向量路由核心区别的理解。

精解：

审题分析：需要判断哪个选项正确描述了链路状态路由的工作方式。
解题思路：回忆LS的核心特征——泛洪LSP、全局视图、独立计算。
完整步骤：
- A错误：LS泛洪的是链路状态分组（LSP），不是完整路由表。路由表是本地计算的结果，不会发送给邻居。泛洪完整路由表是DV的做法。
- B错误：LS通过泛洪机制获取全网的链路状态信息，而非只从邻居获取。只从邻居获取信息是DV的特征。
- C正确：这正是LS的核心工作方式。每个路由器通过泛洪收集到全网的LSP，构建全网拓扑图，然后独立运行Dijkstra算法计算最短路径。
- D错误：根据邻居的路由表更新自己的路由表，这是DV算法的做法。
方法反思：区分LS和DV的关键在于信息获取方式：LS是泛洪获取全局信息，DV是只从邻居获取局部信息。

例题2（中等提升）

题目：某网络有5个节点A、B、C、D、E，链路代价如下：A-B:2, A-C:5, B-C:1, B-D:3, C-D:2, C-E:4, D-E:1。请以A为源节点，使用Dijkstra算法计算A到所有其他节点的最短路径，并给出最终的路由表。

命题意图：考查Dijkstra算法的具体执行过程，这是链路状态路由的核心计算环节。

精解：

审题分析：给定5节点网络的链路代价，需要以A为源运行Dijkstra算法。
解题思路：按Dijkstra算法逐步执行，每轮选择距离最小的未访问节点。
完整步骤：

初始化： $S = \{A\}$ ， $d(A)=0$ ， $d(B)=2$ ， $d(C)=5$ ， $d(D)=\infty$ ， $d(E)=\infty$

第1轮：选 $d(B)=2$ 最小， $S = \{A,B\}$

更新B的邻居： $d(C) = \min(5, 2+1) = 3$ ， $d(D) = \min(\infty, 2+3) = 5$

第2轮：选 $d(C)=3$ 最小， $S = \{A,B,C\}$

更新C的邻居： $d(D) = \min(5, 3+2) = 5$ ， $d(E) = \min(\infty, 3+4) = 7$

第3轮：选 $d(D)=5$ 最小， $S = \{A,B,C,D\}$

更新D的邻居： $d(E) = \min(7, 5+1) = 6$

第4轮：选 $d(E)=6$ 最小， $S = \{A,B,C,D,E\}$ ，算法结束

A的最终路由表：

目的	最短距离	下一跳
B	2	B
C	3	B（经B到C）
D	5	B（经B到D或经B→C→D）
E	6	B（经B→C→D→E或B→D→E）

方法反思：Dijkstra算法的关键是每轮都选当前距离最小的未访问节点，这保证了每次加入 $S$ 的节点其最短路径已被确定。计算时注意更新邻居距离时要取最小值。

五、考情分析

考查频次：近5年出现4-5次，非常高频
常见题型：选择题考查LS与DV的区别；综合题中可能要求执行Dijkstra算法
分值占比：选择题2分，综合题5-8分
命题趋势：Dijkstra算法的具体执行步骤是近年的热门考查点，常与OSPF协议结合出综合题

六、易错点提醒

错误表现：将泛洪（Flooding）理解为"把路由表发给所有邻居"
- 错误原因：混淆了LS的泛洪和DV的周期性通告
- 正确理解：LS泛洪的是链路状态分组（LSP），包含的是"我和哪些邻居相连、代价是多少"的信息，不是路由表
错误表现：执行Dijkstra算法时，在更新邻居距离后忘记重新选择最小距离节点
- 错误原因：将Dijkstra算法理解为"沿路径逐跳推进"
- 正确理解：Dijkstra算法每轮都要从未访问节点中选全局距离最小的，不是沿着某条路径一直走下去
错误表现：认为链路状态路由不会产生任何环路
- 错误原因：对LS的收敛过程理解不全面
- 正确理解：在LS收敛过程中（即各路由器获得的拓扑图不一致的短暂期间），仍然可能出现临时环路。但收敛完成后，由于每个路由器独立计算最短路径树，不会产生环路

七、来源标注

依据2026考研统考大纲
依据《计算机网络（第8版）》谢希仁版
依据《计算机网络：自顶向下方法》Kurose & Ross版

408 > 计算机网络 > 路由算法：链路状态路由 ​

一、定位信息 ​

二、知识点讲解 ​

2.1 基本概念 ​

2.2 工作过程 ​

2.3 Dijkstra算法简述 ​

2.4 LS与DV的详细对比 ​

2.5 LS的优缺点 ​

三、记忆与理解辅助 ​

四、例题与精解 ​

例题1（基础巩固） ​

例题2（中等提升） ​

五、考情分析 ​

六、易错点提醒 ​

七、来源标注 ​