网络抽象：图 链路状态路由算法TIPS：知识出自哈尔滨工业大学李全龙老师的课程讲解。
Djikstra算法
- 所有结点（路由器）掌握网络拓扑和链路费用
- 通过“链路状态广播”
- 所有结点拥有相同信息
- 计算从一个结点（“源”）达到所有其他结点的最短路径
- 获得该结点的转发表
- 迭代：k次迭代后，得到达到k个目的结点的最短路径
符号：
-
c（x，y）：结点x到结点y链路费用；如果x和y不直接相连，则=正无穷
-
D（v）：从源到目的v的当前路径费用值
-
p（v）：沿从源到v的当前路径，v的前序结点
-
N’：已经找到最小费用路径的结点集合
算法复杂性：n个结点
- 每次迭代：需要检测所有不在集合N’中的结点w
- n(n_+1)/2次比较：O(n^2)
- 更高效的实现：
O ( n l o g n ) O(nlogn) O(nlogn)
存在震荡（oscillations）可能：
- e.g.，假设链路费用是该链路承载的通信量：
