Dijkstra在路由选择中的应用
前言背景
OSPF协议(Open Shortest Path First，开放最短路径优先)是在1989年由互联网工程任务组(IETF)正式发布。它能有效地解决RIP和IGRP等距离矢量协议存在的缺陷。具体优点如下：
- 收敛速度快：OSPF采用一种可靠的扩散(flooding)机制根据网络拓扑变化来更新邻居路由器。路由发生改变时只发送产生的路由更新信息。这两点，再加上整个网络在OSPF域中所有路由器上的拓扑都几乎完全一样的特点，使得OSPF在某条链路出现问题时能够比RIP和IGRP更迅速的收敛。
- 支持VLSM、超网以及汇总功能OSPF采用汇总功能和VLSM来节省地址空间。能够更高效地进行路由。
- 存根区域路由：OSPF采用存根区域路由大大减小了路由表的规模。这也是OSPF支持大型网络的一个原因。
- 基于路由代价(Cost)的可变度量OSPF采用可变路由代价度量标准来决定路由选择。
- 支持类型1和类型2(MD5)的认证方式．OSPF能够通过类型1的明文密码或是类型2的MD5加密认证方式来确保安全可靠的路由传输。
原理描述
OSPF区中的每个路由器都具有一个完全相同的链路状态数据库。该链路状态数据库描述了路由器、它们的链路，以及链路的代价。把路由器看作图的顶点，把它们之间的链路看作图的边，把链路的代价看作图的边的权，可把链路状态数据库转换成图。当链路状态数据库转换成一张图后，就可以应用Dijkstra算法来计算出从一点出发到其他所有点的最短路径，即可以计算出路由表。具体的算法如下：把要进行路由计算的路由器加入到最短路径树中，把它所有的邻居加入到可选列表中，并把这些路由器的代价设为刚才加入到最短路径树中的路由器相连的链路代价。接着从可选列表中选出一个代价最小的路由器 加入到最短路径树中，并把它的所有邻居加入到可选列表中。只要可选列表不为空，这个过程一直进行下去。在该算法执行完成后，就可以生成路由器的最短路径树，根据最短路径树，我们就可以得出路由器的路由表。
实验截图
图1
图2
图3
代码
#include
#define N 501 //最大路由器数量
#define INF 100000 //路径最大代价
using namespace std;
int n; //初始路由器数量
int adj[N][N]; //邻接矩阵
void init();
void print();
void ospf(int);
int main()
{
init(); //初始化链路状态
print(); //打印初始链路状态
for(int i=1;i>n;
int x,y,z; //x,y:路由器，z:代价
cout<< "请输入路由器间的连接状态，如路由器1 路由器2 代价,0 0 0表示输入结束"<>x>>y>>z&&!(!x&&!y&&!z))
{
adj[x][y]=z;
adj[y][x]=z;
}
for(int i=1;idis[index]+adj[index][j]&&!vis[j]) //如果通过中间路由器能实现更小代价到达路由器j则更新数组
{
dis[j]=dis[index]+adj[index][j];
next[j]=next[index];
}
}
}
cout<
结果分析
如实验截图中所示，图1是一个无向图，将6个结点看作6台路由器，边上的值看作这条路径的代价，对链路状态进行初始化并打印，如图2。每台路由器通过Dijkstra算法以自身作为源点寻找到达其他路由器的最小代价并打印各自的路由表，如图3。
以路由1到路由6为例，先查路由1的路由表，可以看到到达路由6需要的最小代价为5以及下一跳应该去路由2，再查看路由2的路由表可知要去路由6下一跳应该去路由4，再查看路由4的路由表可知下一跳可以直接到达路由6.Original: https://www.cnblogs.com/LoginX/p/Login_X38.html
Author: 我没有bug
Title: Dijkstra在路由选择中的应用
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/583478/
转载文章受原作者版权保护。转载请注明原作者出处！