寻路算法大总结!
交换机生成树采用的是完全不同的D-V(distance vector)距离矢量算法,并不是很可靠.
并不是任意两点之间的最短路径,因为任意两点之间取最短路径可能有环路:总权更大
交换机STP不一定是最小生成树!!!举例论证 因为它只是所有交换机到根桥最短 贪心算法的味道
kruskal算法也是贪心算法??
| 收敛方式 | 有无环 | 开销 | 批注 |
| 任意两点之间取最短路径, | 最有可能出现环,环数最多. | 总开销最大. | 此时相当于多源最短路径算法得到的收敛地图. |
| 以n-2个点为根,分别让其余n-1个点到自己选择最短路径. | 很有可能出现环,环数很多. | 总开销非常大. | 此时只剩下两个点之间可能不是最短路径. |
| ……以此类推. | 越向上走,越可能出现环,环数越多. | 越往上走,总开销只可能增长不可能减少. |
|
| 以两个点为根,分别让其余n-1个点到自己选择最短路径. | 可能有环. | 总开销再次之. | 此时相当于两棵SPF树出现在同一张网络上.(取并) |
| 以一个点为根,其余n-1个点到自己选择最短路径. | 肯定无环. | 总开销次之. | 此时就是交换机的STP协议. |
| 不考虑根和两点间最短距离,用最短的路径连线连接所有的节点. | 肯定无环. | 总开销最小. | 此时是最小生成树,每对不同节点间相互覆盖的边数最多. |
由欧拉定理得,环数加上n等于边数加1,所以每增加一个环就要增加一条边,相应的就要增加一份开销.
距离矢量路由协议算出来的也是最小生成树;所有SPF树重叠在一起也就是最小生成树.
我们将所有的寻路收敛算法进行统一的思考,这样我们会发现其实他们都属于同一类型的不同程度,就像牛顿把静止也视作一种特殊的运动,因为它是速度为0的运动.