spf算法概述

spf算法即shortest path first 算法–最短路径优先算法，Dijkstra算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径，它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。路由协议中的isis和ospf都使用spf算法计算路由，目的很明确，就是计算路由器自身所在节点到网络拓扑中任意其他节点的cost最小的路径，从而算出路由。
spf算法如何保证根节点到任意节点的路径距离都是最短的呢？因为其总是优先处理cost最小的节点，这就使得有可能拥有更优路径的候选节点不会立即加入集合A，只有当确定路径最优才会加入到树上。

1. 算法概念

Spf：最短路径优先 shortest path first
有向权值图 求取某节点到任意其他节点的最短路径
广度优先算法

2. 具体计算方法

拓扑计算
根节点加入候选链表
运行spf算法直到候选链表为空

1.弹出候选链表中cost最小的节点
2.遍历当前处理节点的所有link（排除回指link，不符条件的Link），如果处理到的link cost比原来的cost大，不处理这个链路。否则替换原来的link。distancen相等则合并。
3.重复步骤1、2，直到候选链表为空

*非根节点，从父节点继承下一跳信息
当
1.父节点是根节点
2.父节点是直连伪节点
时，从link获取下一跳
否则：合并父节点下一跳

计算过程中用到的三个数据库和两个集合：
树数据库I 被明确分配给构造中的树的分枝
候选对象数据库II 候选的分枝
链路状态数据库III 剩余的分支

集合A 被树数据库分支所连接的节点
集合B 其他节点

3. spf算法能保证最短路径的原因

广度优先遍历能保证在遍历到所有link的同时，每次都去取distance最小的结点。在目的节点刚刚加入候选堆中，其distance已经有了一个临时最小值，而这时假若当前连接目的节点的候选分支不是使目的节点cost最小的那个分支，后续弹出节点时必定先算有可能使目的节点distance最小的那些分支，只有当不可能出现更小的distance时，也即此时目的节点的distance在候选堆中最小时，目的节点才会被弹出，加入树数据库，继承下一跳。

4. 路由计算

根据spfnode和spflink算出spf树之后，就可以计算主机路由，后续就可以计算前缀路由。
前缀路由计算需要先优选发布源。优选发布源的，优选最优下一跳，后续获取备下一跳，下路由表。