企业官网建设流程全解析

路由算法的分类

路由算法可以从多个维度进行分类，以下是完整的分类体系：

一、按是否自适应（是否动态更新）

二、按算法策略（⭐最核心的分类）

这是考研最常考的分类方式，共三大类：

1. 距离向量算法（Distance-Vector）

• 核心思想：每个路由器只和邻居交换路由信息，"听邻居的"
• 底层算法：Bellman-Ford 算法
• 代表协议：RIP
• 特点：
  • 只需邻居信息，开销小
  • 收敛慢，存在"计数到无穷"问题
  • 适合小型网络（跳数 ≤ 15）

2. 链路状态算法（Link-State）

• 核心思想：每个路由器掌握全网拓扑，自己计算最短路
• 底层算法：Dijkstra 算法
• 代表协议：OSPF
• 特点：
  • 需要全网信息，开销大
  • 收敛快，无环路
  • 适合大型网络

3. 路径向量算法（Path-Vector）

• 核心思想：不仅记录代价，还记录经过的完整路径（经过哪些AS）
• 代表协议：BGP
• 特点：
  • 用于自治系统（AS）之间
  • 基于策略选路（不仅是"最短"，还要考虑政策）
  • 是整个互联网的路由基础

三、按工作范围

四、按是否考虑当前网络负载

五、其他特殊路由策略（了解）

六、一张图总结

路由算法 ├── 静态路由（手动配置） └── 动态路由（自动更新） ├── 距离向量 ──→ RIP（域内，小型） ├── 链路状态 ──→ OSPF（域内，大型） └── 路径向量 ──→ BGP（域间，互联网）

七、考研重点提醒

必须掌握的：距离向量（RIP）和链路状态（OSPF/Dijkstra）
了解即可的：路径向量（BGP）、洪泛、源路由

最常考的对比题：

Dijkstra 算法与 Bellman-Ford 算法详解

一、Dijkstra 算法（链路状态算法的基础）

1. 核心思想

从源点出发，每一步从未确定最短路径的节点中，选出距离最小的那个，确定其最短路径，然后用它去松弛（更新）邻居的距离。重复直到所有节点确定。

一句话概括：贪心策略——每次选"当前最近的"，逐步扩展。

2. 算法原理

维护两个集合：

• S：已确定最短路径的节点集合
• U：未确定最短路径的节点集合

维护一个数组：

• dist[v]：从源点到 v 的当前已知最短距离（上界估计）

步骤：

初始化： dist[源点] = 0 dist[其他所有节点] = ∞ S = {源点} 循环（直到所有节点加入S）： ① 从 U 中选出 dist 最小的节点 u ② 将 u 加入 S（u 的最短路径确定） ③ 对 u 的每个邻居 v（v ∈ U）： 如果 dist[u] + w(u,v) < dist[v]： dist[v] = dist[u] + w(u,v) ← 松弛操作 记录 v 的前驱为 u

3. 手算示例

给定网络拓扑（无向图）：

2 A -------- B | | 4 | | 1 | | C -------- D 3

求从A到所有节点的最短路径。

解释：

• 第1轮：A的邻居B(2)、C(4)，选B；通过B更新D：2+1=3 < ∞
• 第2轮：U中D(3)、C(4)，选D；通过D更新C：3+3=6 > 4？不，4<6，C保持4？
  等等，让我重新算：A→C=4，D→C=3，所以通过D到C=3+3=6 > 4，C保持4
• 修正：第2轮选D(3)，更新C：min(4, 3+3=6)=4，C不变
• 第3轮：选C(4)

修正后的表：

最终最短路径：A→B=2，A→D=3，A→C=4

4. 代码实现（Python）

import heapq def dijkstra(graph, src): """ graph: 邻接表 {u: [(v, w), ...]} src: 源点 返回: dist字典（源点到各点最短距离） """ dist = {node: float('inf') for node in graph} dist[src] = 0 visited = set() # 最小堆：(距离, 节点) heap = while heap: d, u = heapq.heappop(heap) if u in visited: continue visited.add(u) # ② 确定u的最短路径 for v, w in graph[u]: # ③ 松弛邻居 if v not in visited and d + w < dist[v]: dist[v] = d + w heapq.heappush(heap, (dist[v], v)) return dist

时间复杂度：O((V + E) log V)（使用优先队列）

5. 在路由中的应用（OSPF）

每台路由器： ① 通过 LSA（链路状态通告）洪泛，获得全网拓扑图 ② 以自己为源点，运行 Dijkstra 算法 ③ 得到一棵"最短路径树（SPT）" ④ 根据 SPT 生成路由表（下一跳 = 树上第一跳邻居）

二、Bellman-Ford 算法（距离向量算法的基础）

1. 核心思想

每个节点只和邻居交换信息，反复迭代更新，经过足够多轮后，所有节点的路由表收敛到正确值。

一句话概括：迭代松弛——"问邻居，取最优，再告诉自己的邻居"，反复进行。

2. 算法原理

核心方程（Bellman方程）：

翻译：x 到 y 的最短距离 = 遍历 x 的所有邻居 v，取 "x到v的代价 + v到y的距离" 的最小值。

步骤：

初始化： 对每个节点 x： D_x(x) = 0 ← 到自己距离为0 D_x(y) = ∞ (y≠x) ← 到其他节点未知 迭代（重复多轮）： 对每个节点 x： 对 x 的每个邻居 v： 对每个目的 y： D_x(y) = min( D_x(y), c(x,v) + D_v(y) ) 直到所有 D_x(y) 不再变化 → 收敛

3. 手算示例

同样的拓扑：

2 A -------- B | | 4 | | 1 | | C -------- D 3

以节点A的视角，求到各节点的距离：

初始：A的路由表 → D_A(A)=0, D_A(B)=∞, D_A(C)=∞, D_A(D)=∞

第1轮（A收到邻居B和C的路由表）：

• 邻居B说：D_B(A)=2, D_B(D)=1
• 邻居C说：D_C(A)=4, D_C(D)=3

更新：

• D_A(B) = min(∞, c(A,B)+D_B(B)) = min(∞, 2+0) =2
• D_A(C) = min(∞, c(A,C)+D_C(C)) = min(∞, 4+0) =4
• D_A(D) = min(∞, c(A,B)+D_B(D), c(A,C)+D_C(D)) = min(∞, 2+1, 4+3) =3

第2轮：无变化 →收敛

最终：A→B=2, A→C=4, A→D=3（下一跳分别是B、C、B）

4. 代码实现（Python）

def bellman_ford(graph, src, nodes): """ graph: 边列表 [(u, v, w), ...]（无向图需加反向边） src: 源点 nodes: 所有节点列表 返回: dist字典 """ dist = {node: float('inf') for node in nodes} dist[src] = 0 # 最多迭代 |V|-1 轮 for i in range(len(nodes) - 1): updated = False for u, v, w in graph: if dist[u] + w < dist[v]: dist[v] = dist[u] + w updated = True if not updated: break # 提前收敛 return dist

时间复杂度：O(V × E)

5. 在路由中的应用（RIP）

每台路由器： ① 每隔 30秒，把自己的路由表发给所有邻居 ② 收到邻居的路由表后，用 Bellman 方程更新自己的表 ③ 如果某条路由 180秒 没更新 → 认为不可达（距离=∞） ④ 重复，直到全网收敛

RIP路由表更新规则：

收到邻居 v 发来的路由表： 对其中每条记录 (目的网络 N, 距离 d)： 新距离 = d + 1（加1跳） 如果 路由表中没有 N → 添加 如果 下一跳就是 v → 无条件更新 如果 新距离 < 原距离 → 更新 否则 → 不变

三、两种算法的本质对比

四、为什么 Bellman-Ford 有"计数到无穷"问题？

场景：A—B 链路断了。

正常：A → B，距离=1 断链后：B 不知道 A 不可达，问 C："你去 A 多远？" C 说："2"（C→B→A，但这条路已经断了！） B 更新：到 A = 3 C 再问 B：B 说 3 → C 更新为 4 ... 不断 +1，直到无穷（RIP中为16）

解决方案：

• 水平分割：不把路由信息发回给下一跳来源
• 毒性逆转：把从某邻居学来的路由以"不可达"发回给该邻居
• 触发更新：链路变化立即通知，不等30秒

五、总结图

Dijkstra（OSPF）： 全网地图 → 自己算 → 最短路径树 → 路由表 "我是上帝视角，全局最优" Bellman-Ford（RIP）： 问邻居 → 取最优 → 告诉邻居 → 反复迭代 → 收敛 "我只看一步，大家互相传话，最终趋于正确"