SPF算法1.Dijkstra算法解释(根据E.W.Dijkstra原稿)为了使n个节点之间的全长最小而制作树(a ) )树是在2个节点之间只有1条路径的图。
在我们给出结构的过程中，分歧分为三个集合：
)明确分配给结构树的树枝(他们在子树中)；
)该分支的分隔壁分支被追加到集合1中；
)剩余分支(舍弃还是不考虑)；
节点分为两个集合。
(a )通过集合1内的分支连接的节点；
b :剩下的节点(集合2中只有一个分支指向这些节点中的每个节点)；
那么，就构筑树吧。 首先，选择任意节点作为集合a中唯一的成员，将以该节点为端点的所有分支放入集合。 集合为空。 然后，重复以下两个步骤。
步骤1 )集合中最短的分支被去掉加入到集合中。 结果，一个节点从集合b转发到集合a。 步骤2 :考虑从该节点(刚才发送到集合a的节点)到集合b的节点的分支。 如果构建中的分支比集合的对应分支长，则分支被丢弃； 否则，用它代替集合的对应分支，并且舍弃后者。 然后回到算法的第一步，重复这个过程直到集合和集合b为空。 中的分支形成要求的树
2 .路由器中的最短路径优先算法描述了Djikstra算法中的三个分支集合：、、。 路由器的算法用三个数据库表示这三个分支集合。
**最短路径树数据库**——表示集合。 通过向数据库添加分支，向最短根树添加链接。 算法完成后，该数据库可以描述最短路径树。 *候选数据库**——表示集合。 按照指定顺序从链接状态数据库向该数据库复制链接，作为追加到树中的候补。 **链接状态数据库**——表示集合。 在此保存所有链接。 在Djikstra中，还指定两个节点集合——A、b。 对于此处的节点=路由器。 此写入路由器由路由器三元组(路由器ID、邻居ID、代价)的邻居ID标识。 集合a中的是连接着最短路径树数据库内的链接的路由器。 另一方面，由于集合b中的是其他所有的路由器，所以在算法结束时集合b应该为空。
以下是路由器中最短路径的优选算法版本。
*步骤1** :路由器初始化最短路径树数据库，把自己作为树的根。 路由器是自己的邻居，成本为0。 *步骤2** :在链路状态数据库中，所有描述路由路由器邻居链接的三元组都将添加到候选数据库中。 *步骤3** :计算从根到每个链路的成本，将候选数据库中成本最小的链路反馈移动到最短的路径树数据库。 如果两个或多个链路离开根的成本相同，则随机选择一个移动到最短的树数据库。 *步骤4** :检查添加到最短根树数据库的邻居ID。 除了邻居ID已经在最短根树数据库中的三图之外，链路状态数据库中描述路由器邻居的三图还被添加到候选数据库中。 *步骤5** :如果候选数据库中有剩余项目，请返回步骤3。 如果候选数据库为空，则退出算法。 算法结束后，在最短路径树数据库中，每个单一的近邻ID表表示1台路由器，该算法收敛，最短路径树被构筑。