一步步看懂 OSPF 的 SPF 算法：如何从链路状态计算出最短路径
OSPF 是一种链路状态路由协议，它之所以能帮助数据包找到去往目的地的最佳路径，靠的就是在每一台路由器上独立运行的一个数学算法。这个算法的名字叫SPF（Shortest Path First），也就是经典计算机科学里的Dijkstra 算法。
不过一说“算法”，很多朋友就觉得头疼。没关系，这篇文章会用你能轻易理解的方式，一步步把这个过程拆开来讲。我们不会一上来就丢出一堆术语，而是先从一个生活里的类比开始，再慢慢对应到真实的 OSPF 网络中去。
一、一个生活中的场景：你用导航软件找最短路线
想象你开车去一个陌生城市，手机上的导航软件要帮你找出从当前位置到目的地耗时最短的路线。它是怎么算的呢？肯定不能把所有可能路线都试一遍，太慢了。导航软件的做法大体上是这样的：
- 首先，它手里有一张精细的城市道路图，图上标明了每条路的长度，甚至还能知道实时拥堵情况。
- 它会把自己看作起点，不断向外扩展：“从我这里出发，能直接到哪几条路？每条路要走多久？” 把直接能到的路都标记下来。
- 然后，从这些还没处理过的路里，挑出“离我最近”的一个路口，把它当作“已经找到最佳路线”的点，再从这个路口继续往周围看，看能不能通过它，让去其他路口的距离变得更短。
- 就这样一圈一圈地往外扩，直到计算完所有它能到达的路口为止。
最终，导航软件就能告诉你，到任何一个地方的最快路线，以及需要多长时间。
这正是 Dijkstra 算法的核心思想，也是 OSPF 用来算路的“引擎”。只不过在 OSPF 的世界里，“城市道路”变成了路由器和连接它们的链路，“耗时”变成了 OSPF 的度量值——开销（Cost）。
二、OSPF 的“活地图”是怎么来的？
在导航软件里，地图是事先下好的。在 OSPF 网络里，每台路由器也必须要获得一份完全相同的网络地图，这份地图叫做链路状态数据库（LSDB）。
这个地图是怎么被画出来的呢？靠的是 LSA（链路状态通告）。你可以这样理解：
- 每台路由器都像一个“广播员”，它大声告诉全网络：“我有几根线，分别连着谁，每根线的开销是多少。”
- 这些广播信息（LSA）会被毫无更改地传遍整个网络区域，确保每一台路由器都能听到所有其他路由器的“自我介绍”。
- 最后，每台路由器把收到的所有 LSA 汇总在一起，就在自己脑子里形成了一张包含所有路由器和链路的网络拓扑图。
到这里，大家手里的地图就一模一样了。接下来，每台路由器就要以自己为“我”，在这张图上算出到达所有其它网段的最短路径。
三、用一个简单的三台路由器网络来跑一遍算法
我们先找一个最简单的例子，抛开 OSPF 中那些特殊网络类型（比如以太网广播），只想象有三台路由器，用点对点线路连成一个三角形：
R1 / \ 5/ \10 / \ R2-------R3 4图中数字是链路开销，可以暂时理解成“距离”，越小越快。
现在，我们站在R1的角度，要算出它到 R2 和 R3 的最短路径。执行 Dijkstra 算法时，我们要管理三份“列表”：
- 最短距离表（dist）：记录从 R1 出发，到各个节点的当前已知最短距离。一开始，R1 到自己是 0，到其他所有节点是无穷大（∞）。
- 已确定节点集合（visited）：放那些我们已经找到绝对最短路径的节点，以后不再碰它们。
- 候选节点集合：剩下的、还没处理完的节点。
准备好后，我们开始一步一步地计算。
步骤 1：初始化
- dist[R1] = 0
- dist[R2] = ∞
- dist[R3] = ∞
- visited = {}
- 此时 R1 是起点，也是第一个要处理的“当前节点”。
步骤 2：处理 R1
从未处理的节点中，找 dist 值最小的一个。目前只有 R1 的 dist=0，自然选它。
把 R1 放进 visited，现在它“确定了”。
然后，从 R1 出发看它所有的邻居：
- 到 R2 的直接链路开销是 5。
我们发现，从 R1 到 R2 的新距离 = dist[R1] + 5 = 0 + 5 = 5。
这比原来记录的 ∞ 小得多，所以更新 dist[R2] = 5。 - 到 R3 的直接链路开销是 10。
同理，新距离 = 0 + 10 = 10，比 ∞ 小，更新 dist[R3] = 10。
现在各距离值：
- R1:0 (已确定)
- R2:5
- R3:10
步骤 3：处理 R2
从未确定的节点（R2 和 R3）中，选 dist 最小的。R2 的 5 比 R3 的 10 小，所以这一次选 R2。
把 R2 放进 visited，它现在也确定了。
站在 R2 上看它的邻居（R1 已确定，不管；只关心未确定的）：
- 到 R3 的直接开销是 4。
计算经过 R2 到达 R3 的路径总开销 = dist[R2] + 4 = 5 + 4 = 9。
和 R3 原来的 dist=10 比较，9 更小，所以更新 dist[R3] = 9。
更新后：
- R1:0 (已确定)
- R2:5 (已确定)
- R3:9
步骤 4：处理 R3
只剩下 R3 未确定了，选它。
把 R3 放进 visited。
看 R3 的邻居（R1、R2 都已确定），没有未确定节点需要更新。结束。
最终计算结果：
- R1 到 R2 的最短距离是 5，路径是 R1 → R2。
- R1 到 R3 的最短距离是 9，路径是 R1 → R2 → R3（而不是开销为 10 的直连链路）。
这个过程中最关键的一个操作就是：每当我们确定一个新节点，就用它当作“跳板”，看看能不能帮我们把去其他节点的路变得更短。这叫做“松弛”操作，就像把一根拉紧的绳子放松一样。
四、把这个方法对应到 OSPF 真实行为
上面简单三角形网络帮你理解了算法的骨架，但实际 OSPF 网络要处理的情况稍微复杂一点。主要有两个地方不同，我们稍微解释一下（即使不太明白也没关系，不影响核心理解）：
1. 广播网络的特殊处理
在真实的以太网里，可能多台路由器连在同一个交换机上。这时 OSPF 不会画成全互联的蜘蛛网，而是引入一个“虚拟节点”来代表这个广播网络（叫做伪节点，由 DR 扮演）。算法上，这个伪节点的作用是：
- 路由器到伪节点的开销等于真实链路开销。
- 伪节点到各路由器的开销固定为 0。
这样处理后，最短路径的计算结果依然是正确的。你可以在脑中保留“虚拟节点”这个概念，但这不是初学重点。
2. 从最短距离到路由表
Dijkstra 算法给出的结果，是一棵以 R1 为根的最短路径树，树上有所有路由器和网络节点。但路由器的路由表需要的是“目的网段” 和 “下一跳/出接口”。OSPF 会根据以下原则生成路由：
- 对于树上的叶子节点（通常是末节网络），直接加入路由表，下一跳为沿着路径的第一个下一跳路由器。
- 如果多条路径开销相等，OSPF 会执行等价负载均衡（ECMP），将流量分摊到这几条路径上。
五、为什么路由器不每次重新算一次完整的地图？
你可能会问：每次网络里有条链路断了，就要把整张大地图重新算一遍，那得多累啊？尤其是一些大型 ISP 网络有成百上千台路由器。
没错，所以路由器的操作系统做了优化，这个优化叫增量 SPF（iSPF）。它的大致思路是：
- 如果只是某条链路失效，那它只会影响到一部分节点的最短路径。路由器会记住上一次计算时生成的最短路径树，只把受影响的那部分枝杈砍掉、重新接好，而不是把整棵树连根拔起再种。
这个优化对大型网络非常重要，不过从学习算法的角度，我们只需要知道有这回事就好。
六、SPF 算法的几个重要特性
理解 SPF 算法后，你会更容易明白 OSPF 的一些行为：
- 无环路：因为所有路由器都是基于完全相同的地图计算最短路径树，树的特性决定了从一个点到另一个点只有唯一无环的路径，所以 OSPF 区域内路由永远不会有环路。
- 快速收敛：当网络变化时，一旦新的 LSA 泛洪完成，路由器各自运行 SPF，就可以立刻算出一个新的无环拓扑，这比距离向量协议通过传闻更新要快得多。
- 区域划分的意义：运行 SPF 是很消耗 CPU 的，所以 OSPF 用“区域”把网络切小，每台路由器只需要和区域内路由器保持完全相同的数据库并计算 SPF，区域外的路由用更简单的方法传递，这样就把计算量控制在了可接受范围内。
七、总结
OSPF 的 SPF 算法，说白了就是每个路由器拿到一张全网地图后，自己用 Dijkstra 算法算出以自己为中心的最佳路线图。它的步骤可以浓缩成三句话：
- 从自己开始，把直接连着的邻居距离记下来。
- 选一个当前距离最近的未处理节点，把它“转正”，并用它来尝试缩短到其他未处理节点的距离。
- 重复第 2 步，直到所有节点都处理完。
这个算法虽然简单，但极其健壮，支撑起了全球无数企业网和数据中心的核心路由。希望这篇通俗的讲解能让你再看到“SPF 计算”时，脑子里浮现出的是一个一个“确定”、再“松弛”的有趣过程，而不是一堆冰冷的公式。