链路状态路由算法的实现.docVIP

链路状态路由算法的实现 实验内容与要求 1.程实现右图所示简单网络拓扑的链路状态路由算法。 1.1 结点之间的连接关系固定； 1.2 链路开销可以由用户设定。 2.链路状态算法的实现： 2.1 链路状态消息的交换(可选，简单起见， 可基于静态网络拓扑运行Dijkstra算法)； 2.2 网络拓扑的描述/构造； 2.3 利用Dijkstra算法计算路由； 2.4 路由表的输出。 3.网络拓扑结构的描述(数据结构)，拓扑结构利用文件存储。 4.用可视化界面进行程序演示。 实验环境与知识 实验的运行环境 Windows 7 QTcreator QT4.8 编程语言 C++ 实验的基础知识 算法思想 按路径长度递增次序产生最短路径算法： 把顶点集合V分成两组： （1）S：已求出最短路径的顶点的集合（初始时只含有源点V0） （2）V-S=T：尚未确定最短路径的顶点集合 将T中顶点按最短路径递增的次序加入到S中，保证： （1）从源点V0到S中其他各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度 （2）每个顶点对应一个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度 依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和 （反证法可证） 实验程序的设计流程 设计思路 算法思路的设计 首先，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为∞。显然，长度为 D[j]=Min{D | vi∈V} 的路径就是从v出发的长度最短的一条最短路径。此路径为(v,vj)。 那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。 一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v,vi)上的权值，或者是D[k](vk∈S)和弧(vk,vi)上的权值之和。迪杰斯特拉算法描述如下： 1）arcs表示弧上的权值。若不存在，则置arcs为∞（在本程序中为MAXCOST）。S为已找到从v出发的最短路径的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcs[Locate Vex(G,v),i] vi∈V 2）选择vj，使得D[j]=Min{D | vi∈V-S} 3）修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。 1.2界面的设计与实现 利用QT mainwindow为载体， 添加spinbox 作为输入来源 ， tableview作为输出控件。 与迪杰斯特拉算法类交互。 流程图设 开始 开始 输入路由间的链路的值 输入路由间的链路的值 调用dijkstra算法选择路由 调用dijkstra算法选择路由 更新链路信息 更新链路信息 输出路由表 输出路由表 是否退出 否 是否退出 是 退出 退出 关键的数据结构和代码 关键的数据结构 class dj_arithme{ public: int dj(int,int,int,int,int); int out[20][4]; //起始 目的 距离 下一跳 private: int outrow; int convertout(int,int,int,int); int dist[4][4]; int length[4][4]; int route[4][4]; //下一跳地址存放 int min,minLength,start,end,i,j,n; }; class MainWindow : public QMainWin