《实验十六路由选择算法实验》由会员分享，可在线阅读，更多相关《实验十六路由选择算法实验（3页珍藏版）》请在金锄头文库上搜索。
1、实验十六路由选择算法实验【实验目的】(1) 熟悉网络层中典型的路由选择协议的原理设计方法。(2) 掌握OSPF算法，并将其用自己熟悉的语言实现算法。【实验要求】(1) 在上机前有相应的成熟的算法，对自己程序的流程及源码有所准备;(2) 了解OSPF的适用网络；【实验原理】路由协议(Routing Protocol)是路由器之间实现路由信息共享的一种机制，它允许路由 器之间相互交换和维护各自的路由表。当一台路由器的路由表由于某种原因发生变化时，它 需要及时地将这一变化通知与之相连接的其他路由器，以保证数据的正确传递。路由协议不 承担网络上终端用户之间的数据传输任务。内部网关协议IGP:具体的协议
2、有多种，如RIP和OSPF等。外部网关协议EGP：目前使用的协议就是BGP。OPFS协议路由算法介绍功能：寻找从某个源点到其余各顶点的最短路径原理：按路径长度递增的顺序产生各个顶点的最短路径。对于如图1所示的网络连接图，图1圍络连接图引入一个距离向量D，它的每一个分量Di表示从源点v0到每个终点vi的最短路径长 度。距离向量的初始值用下面方法确定：如果v1到终点vi有边，则Di为边长，否则Di 为8。则图的初始距离向量为：D=8 ,2,5, 1,8,8。如果已经找到了第一条最短路径(v1, vi)则下一个找到的最短路径是哪一条？设该顶点的终点为vk(如何找到vk?)则这条路径要么为(v1, v
3、k)，要么为(v1, vi, vk)即找到最短路径长度Di后，更新剩下所有的最短路径长度Dj=Min(v1, vj), (v1, vi, vk),最小的Dj即为次短的最短路径。以此类推。算法步骤描述如下：1.用邻接矩阵arcs表示有向图。S为找到最短路径的目标结点的集合,V为图中所有点 的集合2. 算法开始时S为空集，设出发点为vl ,则辅助向量D的初始值为R ,2,5, 1,8, oo3. 选择vj ,使得Di=MinDk|vk V-S，则Vi就是当前找到最短路径的目标结点, 令 S=S U Vi。4. 修改从V1出发到集合V-S上任一点Vk的当前最短路径长度，如果Di+arcsikvDk,
4、则修改 Dk为 Dk= Di+arcsik5. 重复3、4共n-1次(有向图有n个顶点)【实验步骤】#includeiostream.h#includestdlib.h#define MAXPOINT 3/定义最大的顶点数目#define limit 32767/设置没有路径的权代替无穷大struct record/没个顶点的数据结构设置为一个数组队列int number; 顶点号int flag;标志是否从队列中被选过如果为1表示选过为0表示未选int allpath; 从源点到这个点的当前最短距离(权最小)pathMAXPOINT+1;int costMAXPOINT+1MAXPOINT+
5、1; / 用来表示图的邻接矩阵void main()int i,j,temp,front=1,rear=MAXPOINT,N,minnumber;/temp表示在数组队列中的当前下标front表示队列首rear表示队列尾/N表示待输入的源点号码minnumber表示选中的点的号码int min=32768;设置一个初始值for(i=1;i=MAXPOINT;i+)for(j=1;jcostij;/初始化所有点之间的(权)路径值 /coutvv请输入源点号vvendl; /输入一个起点 cinN;for(N=MAXPOINT;N=1;N-)把每一个点轮流地都设置为起点，可以求出任意一对顶点之间的
6、最短路径 for(i=front;iv=rear;i+) /初始化每个点的信息if(i=N)pathi.allpath=O;elsepathi.allpath=limit;pathi.flag=0;pathi.number=i;while(rear=l)/控制循环次数for(temp=front;tempv=MAXPOINT;temp+)if(pathtemp.allpathvm in& pathtemp.flag=O)/选出一个具有最值的点 minnumber=pathtemp.number;min=pathtemp.allpath ;min=32768;pathminnumber.flag
7、=1;/把选中的点的标志变量置1表示已经被选过避免选中for(i=1；iv=MAXPOINT;i+)/进行类似广度优先搜索，更新最短路径 if(i!=minnumber)&( pathminnumber.allpath+costminnumberivpathi.allpath) pathi.allpath=pathminnumber.allpath+costminnumberi;rear-;/次数减 1rear=MAXPOINT; 恢复数组以便于下一点的循环for(j=1;j=MAXPOINT;j+) coutvv第vvNvv点到第vvjvv点的最短路径长度(权)为;coutvvpathj.allpath vvendl;
