链路状态路由算法实验.doc
Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date链路状态路由算法实验链路状态路由算法实验实验二 链路状态路由算法的实验一、实验目的：了解链路状态路由算法的原理以及具体过程。二、实验原理： 链路状态算法实现的基本步骤：1、发现他的邻接点，并知道其网络的地址。2、测量到各邻接点的延迟或开销。3、构造一个分组，分组中包含所有他刚刚收到的信息。4、将这个分组发送给其他的路由器。5、计算出到每一个其他路由器的最短路径三、链路状态路由的核心算法（迪加克拉算法）：void dijkstra(int s, int t, int path) struct state /存放节点数据 int predecessor; /父节点 int length; /权值 bool lable; /访问状态 stateMAX_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 = 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 = statei.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、不同两点间的最短路径： 六、 源代码#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_NODES; 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 << "个节点的权值：" << endl; 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<<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->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.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 << 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 >> 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 >> 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：" <<endl; cin >> i; cout << "输入要修改的结点2：" <<endl; cin >> j; cout << "输入修改的权值：" <<endl; cin >> disti-1j-1; void displayRouteInfo() cout << "*" << endl; cout << "路由表信息:" << endl; for(int 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 >> Vnums;do/主菜单界面cout << "t" <<"=" << endl;cout << "t" <<"1.创建路由表" << endl;cout << "t" <<"2.增加路由" << endl;cout << "t" <<"3.删除路由" << endl;cout << "t" <<"4.修改路由" << endl;cout << "t" <<"5.找两个路由间的最短路径" << endl;cout << "t" <<"6.保存路由表到文件" << endl;cout << "t" <<"7.显示路由表信息" << endl;cout << "t" <<"8.退出" << endl;cout << "t" <<"=" << endl;/cout << "输入路由总节点数：" << endl;/cin >> Vnums;cout << "选择操作(1-8)：" << endl;cin >> change;switch(change) case 1: creatRouteMap(Vnums); 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"); system("cls"); break; case 6:routeTables.open(routeTable); if(routeTables=NULL) cout << "打开文件夹错误:" << endl; getchar(); exit(0); /保存文件 saveRoute(routeTables); routeTables.close(); system("cls"); break; case 7: displayRouteInfo();system("pause");system("cls"); break; case 8: return 0; default: system("cls"); break; cout << "返回选择菜单(y 或者 n)：" << endl; cin >> ch; if(ch = 'n') break; while(ch = 'y');system("pause");return 0;七、 心得体会：通过做练习编写链路状态路由算法的实验，我更进一步加深了对链路状态路由原理的理解，对网络过程中网络节点的信息传输与通信有了更进一步认识。同时，对迪加克拉求最短路径算法的设计与原理加深了理解。-
