算法随后再次迭代。当候选列表变为空时，算法终止。
以下步骤详细描述该算法。请记住，我们正在计算 Area A 的最短
路径树。下文中所有对链路状态数据库查找的引用都是针对 Area A
的数据库。
(1) 初始化算法的数据结构。清空候选顶点列表。把最短路径树
初始化为只包含根（即执行该计算的路由器）。把 Area A 的
TransitCapability 设为 FALSE。
(2) 把刚加入树中的顶点称为顶点 V。检查与顶点 V 关联的 LSA。
这是基于 Vertex ID 在 Area A 的链路状态数据库中做一次
查找。如果这是一个 router-LSA，且该 router-LSA 的 bit V
（见 A.4.2 节）被置位，则把 Area A 的 TransitCapability
设为 TRUE。无论哪种情况，该 LSA 所描述的每条链路都给出了
到某个相邻顶点的代价。对于所描述的每条链路（假设它连接
顶点 V 与顶点 W）：
(a) 如果这是一条到 stub network 的链路，则检查 V 的 LSA
中的下一条链路。到 stub network 的链路将在最短路径
计算的第二阶段中考虑。
(b) 否则，W 是一个 transit 顶点（router 或 transit
network）。在 Area A 的链路状态数据库中查找顶点 W 的
LSA（router-LSA 或 network-LSA）。如果该 LSA 不存在，
或其 LS age 等于 MaxAge，或它没有一条回到顶点 V 的
链路，则检查 V 的 LSA 中的下一条链路。[23]
(c) 如果顶点 W 已经在最短路径树上，则检查该 LSA 中的
下一条链路。
(d) 计算由此得到的从根到顶点 W 的路径的链路状态代价 D。
D 等于（已计算出的）到顶点 V 的最短路径的链路状态
代价，加上顶点 V 与 W 之间链路的通告代价。如果 D：
o 大于候选列表上顶点 W 已有的取值，则检查下一条
链路。
o 等于候选列表上顶点 W 的取值，则计算使用该通告
链路所产生的下一跳集合。该计算的输入是目的地
（W）及其父节点（V）。该计算在 16.1.1 节中说明。
这组下一跳应被加入候选列表上 W 已有的下一跳取值中。
o 小于候选列表上顶点 W 的取值，或者 W 尚未出现在
候选列表上，则把候选列表上 W 的条目设为表示距根
距离为 D。同时计算使用该通告链路所产生的下一跳
列表，并相应地设置 W 的下一跳取值。下一跳计算在
16.1.1 节中描述；它以目的地（W）及其父节点（V）
为输入。
(3) 如果在这一步候选列表为空，则（transit 顶点的）最短路径树
已完全构建完毕，该阶段的过程终止。否则，选择候选列表中
离根最近的那个顶点，把它加入最短路径树（同时把它从候选
列表中移除）。注意，当有多个顶点同为离根最近时，必须先
选择 network 顶点再选择 router 顶点，这样才能必然地找到
所有等价路径。这与 OSPF 组播路由扩展（MOSPF）所使用的
改进 Dijkstra 算法中引入的决胜规则是一致的。
(4) 可能需要修改路由表。对于那些被修改的路由表条目，其关联
区域将被设为 Area A，path type 将被设为 intra-area，
cost 将被设为新发现的最短路径的计算距离。
如果新加入的顶点是一台 area border router 或 AS boundary
router，则添加一个 destination type 为 "router" 的路由表
条目。与之关联的 router-LSA 中的 Options 字段被复制到该
路由表条目的 Optional capabilities 字段中。把新加入的顶点
称为 Router X。如果 Router X 是执行计算的路由器所配置的
某条 virtual link 的端点，且该 virtual link 以 Area A 作为
Transit area：则宣告该 virtual link 为 up，把 virtual
interface 的 IP 地址设为上面为 Router X 计算出的出向接口
的 IP 地址，把 virtual neighbor 的 IP 地址设为 Router X
的那个指回最短路径树根的接口地址（包含在 Router X 的
router-LSA 中）；等价地说，这就是那个指回 Router X 在最短
路径树上父顶点的接口（类似于 16.1.1 节中的计算）。
如果新加入的顶点是一个 transit network，则定位该网络的
路由表条目。该条目的 Destination ID 是 IP 网络号，可以
通过用其关联的子网掩码（在相应 network-LSA 的正文中）对
Vertex ID（Link State ID）做掩码运算得到。如果该路由表
条目已经存在（即路由表中已安装了到该目的地的一条
intra-area 路由），说明有多个顶点映射到了同一个 IP 网络。
例如，当一个新的 Designated Router 正在建立时就会发生这种
情况。此时，当且仅当新找到的路径同样短，并且当前路由表
条目的 Link State Origin 的 Link State ID 小于新加入顶点
的 LSA 时，才应覆盖当前的路由表条目。
如果该网络没有路由表条目（通常情况），则应为该 IP 网络
添加一个路由表条目。该路由表条目的 Link State Origin
应设为新加入顶点的 LSA。
(5) 返回步骤 2 以迭代该算法。
stub network 在该过程的第二阶段被加入树中。在这一阶段，再次
检查所有 router 顶点。在上述第一阶段中被判定为不可达的那些
顶点被丢弃。对于每个可达的 router 顶点（称之为 V），在链路
状态数据库中找到与之关联的 router-LSA。然后检查该 LSA 中出现
的每条 stub network 链路，并执行以下步骤：
(1) 计算该 stub network 距根的距离 D。D 等于从根到该 router
顶点的距离（在第 1 阶段中计算得出），加上该 stub network
链路的通告代价。把这个距离与到该 stub network 的当前最佳
代价进行比较。这通过查找该 stub network 当前的路由表条目
来完成。如果计算出的距离 D 较大，则继续检查该 LSA 中的
下一条 stub network 链路。
(2) 如果执行到这一步，则必须更新该 stub network 的路由表条目。
计算使用该 stub network 链路所产生的下一跳集合。该计算在
16.1.1 节中说明；该计算的输入是目的地（该 stub network）
和父顶点（该 router 顶点）。如果距离 D 与当前路由表代价
相同，则只需把这组下一跳加入该路由表条目的下一跳列表。
在这种情况下，路由表已经有一个 Link State Origin。如果这个
Link State Origin 是一个 router-LSA，且其 Link State ID
小于 V 的 Router ID，则把 Link State Origin 重置为 V 的
router-LSA。
否则 D 小于路由表代价。通过把该路由表条目的代价设为 D，
并把该条目的下一跳列表设为新计算出的集合，来覆盖当前的
路由表条目。把该路由表条目的 Link State Origin 设为 V 的
router-LSA。然后继续检查下一条 stub network 链路。
对于在第二阶段中添加/修改的所有路由表条目，其关联区域将被设为
Area A，path type 将被设为 intra-area。当可达 router-LSA 的
列表被检查完毕时，第二阶段即告完成。此时，
与 Area A 关联的所有 intra-area 路由都已确定。
本规范并不要求必须使用上述两阶段方法来计算最短路径树。但是，
如果使用另一种算法，它必须产生完全相同的树。因此，必须注意：
transit 顶点之间的链路必须是双向的，才能被包含进上述树中。
还应提到，存在计算该树的更高效算法；例如 [Ref1] 中描述的
增量 SPF 算法。
16.1.1. 下一跳计算（The next hop calculation）
本节解释如何计算某个目的地所使用的当前下一跳集合。每个
下一跳由向该目的地转发报文时所使用的出向接口，以及下一跳
路由器的 IP 地址（如果有的话）组成。每当发现一条通向该
目的地的更短路径时，就会调用下一跳计算。这可能发生在最短
路径树计算的任一阶段（见 16.1 节）。在最短路径树计算的
第 1 阶段，当目的地被加入候选列表时，或当候选列表上该
目的地的条目被修改时（第 1 阶段的步骤 2d），就发现了一条
更短的路径。在第 2 阶段，每当该目的地的路由表条目被修改
时（第 2 阶段的步骤 2），就发现了一条更短的路径。
随着越来越短的路径被发现，该目的地所使用的下一跳集合在
最短路径树计算过程中可能被重新计算多次。最终，该目的地的
路由表条目将总是反映由绝对最短路径所产生的下一跳。
下一跳计算的输入是 a) 目的地，以及 b) 它在根（执行计算的
路由器）与目的地之间当前最短路径上的父节点。父节点总是
一个 transit 顶点（即总是一台路由器或一个 transit
network）。
如果在目的地与根之间的当前最短路径上至少存在一台中间
路由器，则该目的地直接从其父节点继承下一跳集合。否则，
有两种情况。在第一种情况下，父顶点就是根（执行计算的
路由器自身）。这意味着目的地要么是一个直连网络，要么是
一台直连路由器。此时出向接口就是连接到该目的网络/路由器
的那个 OSPF 接口。如果目的地是一台通过 Point-to-MultiPoint
网络与执行计算的路由器相连的路由器，则可以通过检查该目的
路由器的 router-LSA 来确定其下一跳 IP 地址：每条指回执行
计算的路由器、且其 Link Data 字段属于该 Point-to-MultiPoint
网络的链路，都提供了一个下一跳路由器的 IP 地址。如果目的地
是一个直连网络，或者是一台通过 point-to-point 接口与执行
计算的路由器相连的路由器，则不需要下一跳 IP 地址。如果
目的地是一台通过 virtual link 与执行计算的路由器相连的
路由器，则下一跳的设置应推迟到 16.3 节中的计算。
在第二种情况下，父顶点是一个把执行计算的路由器直接连接到
目的路由器的网络。此时通过检查目的地的 router-LSA 来确定
下一跳列表。对于该 router-LSA 中每条指回该父网络的链路，
该链路的 Link Data 字段提供了一个下一跳路由器的 IP 地址。
所使用的出向接口随后可以从该下一跳 IP 地址推导得出（也
可以从父网络继承）。
16.2. 计算 inter-area 路由
inter-area 路由通过检查 summary-LSA 来计算。如果路由器有到
多个区域的活动连接，则只检查 backbone 的 summary-LSA。只接入
单个区域的路由器则检查该区域的 summary-LSA。无论哪种情况，
下面所检查的 summary-LSA 都属于单个区域的链路状态数据库
（称之为 Area A）。