链路状态路由算法实验

1、实验二 链路状态路由算法的实验一、实验目的：了解链路状态路由算法的原理以及具体过程。二、实验原理： 链路状态算法实现的基本步骤：1、发现他的邻接点，并知道其网络的地址。2、测量到各邻接点的延迟或开销。3、构造一个分组，分组中包含所有他刚刚收到的信息。4、将这个分组发送给其他的路由器。5、计算出到每一个其他路由器的最短路径三、链路状态路由的核心算法（迪加克拉算法）：void dijkstra(int s, int t, int path) struct state /存放节点数据 int predecessor; /父节点 int length; /权值 bool lable; /访问状态 st

2、ateMAX_NODES; int i,j,k,min; struct state *p; for(p = &state0; p < &stateVnums; p +) /初始化节点数据 p->predecessor = -1; p->length = INFINITY; p->lable = false;statet.length = 0;statet.lable = true;k = t;do for(int i = 0; i < Vnums; i +) if( (distki != 0) && (statei.lable =

3、false) if(statek.length + distki < statei.length) statei.predecessor = k; /记录节点 cout << k << "->" statei.length = statek.length + distki; /路径长度 k = 0;min = INFINITY; for(int i = 0; i < Vnums; i +) if(statei.lable = false) && (statei.length < min) min = state

4、i.length; k = i; statek.lable = true; while(k!=s); cout << s; 四、流程图：核心算法（迪加克拉算法）流程图：访问起始路由K，目标s statei.lable = falsei+计算statek.lengthstatei.predecessor = kk=0; min = INFINITY;statei.lable = false) && (statei.length < min)k=i;i+statek.lable = true;k=s 结束五、 程序截图：1、 路由表信息： 2、不同两点间的最短路径

5、： 六、 源代码#include <iostream>#include <fstream>#define routeTable "routeTable.txt"using namespace std;const int MAX_NODES = 1024; const int INFINITY = 100000;int distMAX_NODESMAX_NODES; /用于存放网络拓扑结构连接矩阵 int static Vnums; /总的节点数 void initDist() /初始化邻接矩阵 for(int i = 0; i < MAX_NO

6、DES; i +) for(int j = 0; j < MAX_NODES; j +) distij = 0; void creatRouteMap(int Vnums) /创建网络拓扑结构的邻接矩阵 for(int i = 0; i < Vnums; i +) cout << "输入第" << i << "个节点与第" ; for(int j = 0; j < Vnums; j +) cout << j << "个节点的权值：" << end

7、l; cin >> distij; void saveRoute(ofstream& routeTables) /保存路由信息 routeTables << "路由邻接矩阵为：" routeTables << "n" routeTables << "*" routeTables << "n" for(int i = 0; i < Vnums; i +) for(int j = 0; j < Vnums; j +) routeTables

8、<<distij<<"t" routeTables << "n" void dijkstra(int s, int t, int path) struct state /存放节点数据 int predecessor; /父节点 int length; /权值 bool lable; /访问状态 stateMAX_NODES; int i,j,k,min,print; struct state *p; for(p = &state0; p < &stateVnums; p +) /初始化节点数据 p

9、->predecessor = -1; p->length = INFINITY; p->lable = false;statet.length = 0;statet.lable = true;k = t;cout << "最短路径为：" << endl;do for(int i = 0; i < Vnums; i +) if( (distki != 0) && (statei.lable = false) if(statek.length + distki < statei.length) statei

10、.predecessor = k; /记录节点 cout << k << "->" statei.length = statek.length + distki; /路径长度总和 k = 0; min = INFINITY; for(int i = 0; i < Vnums; i +) if(statei.lable = false) && (statei.length < min) min = statei.length; k = i; statek.lable = true; while(k!=s); cout

11、<< s; void addRoute() /添加一个路由及结点信息 char ch; do cout << "添加一个路由:" << endl; Vnums = Vnums + 1; cout << "输入第" << Vnums - 1 << "个节点与第" ; for(int j = 0; j < Vnums; j +) cout << j << "个节点的权值：" << endl; cin >

12、;> distVnums - 1j; /对应行的信息 distjVnums - 1 = distVnums - 1j; /对应列的信息 cout << "继续添加(y 或者 n)：" << endl; cin >> ch; if(ch = 'n') break; while(ch = 'y'); void deleteRoute() char ch; int delNum; do cout << "输入删除路由结点号:" << endl; cin >&

13、gt; delNum; for(int j = 0; j < Vnums; j +) distdelNum - 1j = 0; /对应行的信息 distjdelNum - 1 = distdelNum - 1j; /对应列的信息 cout << "继续删除(y 或者 n)：" << endl; cin >> ch; if(ch = 'n') break; while(ch = 'y'); void changeRoute() int i,j; cout << "输入要修改的结点1

14、：" <<endl; cin >> i; cout << "输入要修改的结点2：" <<endl; cin >> j; cout << "输入修改的权值：" <<endl; cin >> disti-1j-1; void displayRouteInfo() cout << "*" << endl; cout << "路由表信息:" << endl; for(in

15、t i = 0; i < Vnums; i +) for(int j = 0; j < Vnums; j +) cout << distij << "t" cout << "n" int main()int desNode,rouNode;int pathMAX_NODES;int change; char ch;ofstream routeTables;/初始化权值矩阵 initDist();cout << "输入路由总节点数：" << endl;cin >

16、;> Vnums;do/主菜单界面cout << "t" <<"=" << endl;cout << "t" <<"1.创建路由表" << endl;cout << "t" <<"2.增加路由" << endl;cout << "t" <<"3.删除路由" << endl;cout <

17、;< "t" <<"4.修改路由" << endl;cout << "t" <<"5.找两个路由间的最短路径" << endl;cout << "t" <<"6.保存路由表到文件" << endl;cout << "t" <<"7.显示路由表信息" << endl;cout << &quo

18、t;t" <<"8.退出" << endl;cout << "t" <<"=" << endl;/cout << "输入路由总节点数：" << endl;/cin >> Vnums;cout << "选择操作(1-8)：" << endl;cin >> change;switch(change) case 1: creatRouteMap(Vnums);

19、system("pause"); system("cls");break;case 2:addRoute(); system("pause"); system("cls"); break; case 3: deleteRoute(); system("pause"); system("cls"); break; case 4:changeRoute(); system("pause"); system("cls");break;case 5: cout << "输入目标节点和源节点：" << endl; cin >> desNode; cin >> rouNode; dijkstra(desNode,rouNode,path); /求最短路径 system("pause");