spf算法概述
文章目录
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树之后，就可以计算主机路由，后续就可以计算前缀路由。
前缀路由计算需要先优选发布源。优选发布源的，优选最优下一跳，后续获取备下一跳，下路由表。