距离向量路由算法实验报告.doc

信息安全_专业 1002_班 2012年12月20日 姓名吴文珊 学号_09091025251 实验题目 模拟距离向量路由算法的路由表交换过程，演示每轮交换后路由表的变化，动态生成网络拓扑图，从初始路由表开始，进行交换路由表，演示每轮交换后的路由表的变化。观察和讨论多少轮交换后路由表稳定。2 需求分析本程序用C编写，完成距离向量路由算法的模拟。(1)输入的形式与输出值的范围：输入时要求输入节点个数、初始网络拓扑图中边的条数（即：邻居节点的对数），节点名称、每条边的弧头、弧尾节点、边权值。名字定义为字符串形式，节点个数、边条数、边权值为整形变量；(2)输出的形式：输入信息后，程序输出每轮交换之后新的的路由表(3)程序所能达到的功能：完成节点信息的输入、随机选取节点交换向量，并更新路由表，显示经过多少轮交换路由表稳定，并停止交换。(4)测试数据：节点个数：4 边条数 ：4节点名称：a b c d 弧头 弧尾 权值 a b 3 b d 6 c a 2 d a 6最终距离向量矩阵如下： a b c d a 0 3 2 6 b 3 0 5 6 c 2 5 0 8 d 6 6 8 03 概要设计 (1)为了实现上述功能，须定义结构体的抽象数据类型(2)本程序包含了 个函数：void visit(VertexType ver)/访问顶点的函数void input(VertexType &ver) /输入顶点信息的函数 int LocateVex(MGraph G,VertexType u)/查找顶点u,并返回void CreateDN(MGraph &G)/构造有向网G GetVex(MGraph G，int v)/得到图中顶点Vvoid Display(MGraph G)/显示路由表void ShortestPath_Floyd()各函数间关系如下：CreateDN()LocateVex() visit()Main() Display() GetVex() ShortestPath_Floyd()4 详细设计实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。(1) 节点类型 struct VertexType/最简单的顶点信息类型(只有顶点名称)char nameMAX_NAME;/顶点名称 char routersMAX_VERTEX_NUMMAX_NAME;/定义最短路径中到目的节点的上一跳 ;struct MGraph/图的结构VertexType vexsMAX_VERTEX_NUM;/顶点向量AdjMatrix arcs;/邻接矩阵(二维数组)int vexnum,arcnum;/图的当前顶点数和弧数GraphKind kind; /图的种类标志 ;typedef struct /边(弧)信息结构VRType adj;/顶点关系类型，对带权图，表示权值 struct VertexType/最简单的顶点信息类型(只有顶点名称)char nameMAX_NAME;/顶点名称 char routersMAX_VERTEX_NUMMAX_NAME;/定义最短路径中到目的节点的上一跳 ;struct MGraph/图的结构VertexType vexsMAX_VERTEX_NUM;/顶点向量AdjMatrix arcs;/邻接矩阵(二维数组)int vexnum,arcnum;/图的当前顶点数和弧数GraphKind kind; /图的种类标志 ;(2)各功能函数伪码算法 main() CreateDN(g);/构造有向网g for(i=0;ig.vexnum;i+) g.arcsii.adj=0;/顶点到自身距离为0 Display(g);/输出有向网g ShortestPath_Floyd(g,p,d);/求每对顶点的最短路径 return 1; void CreateDN(MGraph &G)/构造有向网G scanf(%d %d,&G.vexnum,&G.arcnum); for(i=0;iG.vexnum;i+)/构造顶点向量 input(G.vexsi); /输入节点名称 for(i=0;iG.vexnum;i+)/初始化二维邻接矩阵 for(j=0;jG.vexnum;j+) G.arcsij.adj=INFINITY; for(k=0;kG.arcnum;k+) scanf(%s %s %d,,,&w); 存入图中； void Display(MGraph G)for(i=0;iG.vexnum;i+)visit(GetVex(G,i);for(i=0;iG.vexnum;i+) printf(%-8s,G.); for(j=0;jG.vexnum;j+) printf(%20s,G.); for(k=0;kG.vexnum;k+) printf( %-5d,G.arcsjk.adj); printf(n); void ShortestPath_Floyd()/用Floyd算法随机更新两顶点间最短路径、顶点路由表，若Pvwu为true，则u是从v到w当前求得最短路径上的顶点for(v=0;vG.vexnum;v+)for(w=0;wG.vexnum;w+)Dvw=G.arcsvw.adj;/顶点v到w的直接距离for(u=0;uG.vexnum;u+)Pvwu=FALSE;if(DvwINFINITY)/从V到W有直接路径 strcpy(G.vexsv.routersw,G.);Pvwv=Pvww=TRUE; /由v到w的路径经过v和w两点 else strcpy(G.vexsv.routersw,-); srand(unsigned)time(NULL);/产生随机数种子，防止伪随机数 while(change=1) for(;bad20;)/连续20次随机交换无更新，为坏的交换，则停止随机交换 v=rand()%G.vexnum;w=rand()%G.vexnum;if(DvwINFINITY&v!=w) change=0; for(u=0;uG.vexnum;u+) if(DwuINFINITY&Dvw+DwuDvu)/从v经u到w的一条路径更短 Dvu=Dvw+Dwu;/更新最短距离 change=1; bad=0; /一有更新，则不是坏的交换 if(w!=u) strcpy(G.vexsv.routersu,G.);/记录上一跳节点名称 for(i=0;iG.vexnum;i+) Pvwi=Pvui|Puwi;/从v到w的路径经过从v到u和从u到w的所有路径 /if /for u if(change=1) stable+; for(j=0;jG.vexnum;j+) printf( %8s %8d %8sn,G.,Dvj,G.vexsv.routersj); / if change else bad+; /if/for /while for(i=0;iG.vexnum;i+) printf(%-8s,G.); for(j=0;jG.vexnum;j+) printf(%20s,G.); for(k=0;kG.vexnum;k+) printf( %-5d,Djk); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) printf( %8s %8d %8sn,G.,Dij,G.vexsi.routersj); 5 设计过程中遇到的问题：开始时，设计思路一直停留在弗洛伊德算法中，这是我们数据结构课程中介绍的求最短距离算法，输入节点信息后，由程序自动加入n个节点进行试探（对任意两个节点，它们之间的最短距离必然经过n个中间节点，0nN），一有更短距离则进行更新并记录，这也是动态规划的思想。但是实验要求动态生成网络拓扑图，在老师的提醒下，我做了改进。随机生成顶点序号，若两节点是邻居节点，则让两节点进行交换路由向量，再进行更新。但是又出现了另一个问题：无穷交换，因为在设置循环交换条件时出现了问题，于是记录是否交换，若到达一定次数的交换都未成功更新路由表，则认为路由表已稳定，停止交换。但是通过多次试验，发现经常在路由表还未稳定时，循环就结束。究其原因，发现是“未更新的次数”这个标记变量有随机性，因为定义这个变量时，是“从开始交换，到交换到某个时刻，未更新的次数累加”。于是将这个变量改为“若连续n次随机选取节点进行交换时，路由表都未更新，则视为bad交换，认为路由表已稳定，一旦有更新，则bad清0”。虽然采取这种方法，有时候也会出现提前结束，但是也是在极少情况下，比如随机选取节点时一直选择重复节点，为避免这个问题，使用srand()函数产生随机数种子，防止伪随机数。问题得到极大改善 六源程序清单#include#include#include#include#include#include#include#include#include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define MAX_NAME 9/顶点名称字符串最大长度+1#define INFINITY 1000/用1000代替#define MAX_VERTEX_NUM 26 /最大顶点个数typedef int Status;typedef int Boolean;typedef int VRType;/定义顶点关系类型为整型，与INFINITY的类型一致typedef char PathMatrixMAX_VERTEX_NUMMAX_VERTEX_NUMMAX_VERTEX_NUM;/三维数组typedef VRType DistancMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/二维数组 typedef struct /边(弧)信息结构VRType adj;/顶点关系类型，对带权图，表示权值 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/二维数组 enum GraphKindDG,DN,UDG,UDN ;/有向图、无向网、无向图、无向网struct VertexType/最简单的顶点信息类型(只有顶点名称)char nameMAX_NAME;/顶点名称 char routersMAX_VERTEX_NUMMAX_NAME;/定义最短路径中到目的节点的上一跳 ;struct MGraph/图的结构VertexType vexsMAX_VERTEX_NUM;/顶点向量AdjMatrix arcs;/邻接矩阵(二维数组)int vexnum,arcnum;/图的当前顶点数和弧数GraphKind kind; /图的种类标志 ;int stable=0;/到达稳定前路由表交换次数 void visit(VertexType ver)/访问顶点的函数printf(%s,);void input(VertexType &ver) /输入顶点信息的函数 scanf(%s,);int LocateVex(MGraph G,VertexType u)/查找顶点u,并返回其位置int i;for(i=0;iG.vexnum;+i)if(strcmp(,G.)=0)return i;void CreateDN(MGraph &G)/构造有向网G int i,j,k;VRType w;/顶点关系类型 VertexType v1,v2; printf( 请输入网络拓扑结构中的节点数、弧数); scanf(%d %d,&G.vexnum,&G.arcnum); printf( 请输入%d个顶点的值（名称小于%d个字符）：,G.vexnum,MAX_NAME); for(i=0;iG.vexnum;i+)/构造顶点向量 input(G.vexsi); /输入节点名称 for(i=0;iG.vexnum;i+)/初始化二维邻接矩阵 for(j=0;jG.vexnum;j+) G.arcsij.adj=INFINITY; printf( 请输入%d条弧的弧尾 弧头 权值：n,G.arcnum); for(k=0;k=G.vexnum|v0)exit(OVERFLOW);return G.vexsv;void Display(MGraph G)int i,j,k;printf( %d个顶点%d条弧的无向网。顶点依次是：,G.vexnum,G.arcnum);for(i=0;iG.vexnum;i+)visit(GetVex(G,i);printf(n 初 始 路 由 表 如 下(1000表示无穷远):n); printf( );for(i=0;iG.vexnum;i+) printf(%-8s,G.); printf(n); for(j=0;jG.vexnum;j+) printf(%20s,G.); for(k=0;kG.vexnum;k+) printf( %-5d,G.arcsjk.adj); printf(n); void ShortestPath_Floyd(MGraph G,PathMatrix P,DistancMatrix D)/用Floyd算法随机更新两顶点间最短路径、顶点路由表，若Pvwu为true，则u是从v到w当前求得最短路径上的顶点int u,v,w,i,j,k;int change=1;/路由表有无交换 int bad=1;/不好的交换 for(v=0;vG.vexnum;v+)for(w=0;wG.vexnum;w+)Dvw=G.arcsvw.adj;/顶点v到w的直接距离for(u=0;uG.vexnum;u+)Pvwu=FALSE;if(DvwINFINITY)/从V到W有直接路径 strcpy(G.vexsv.routersw,G.);Pvwv=Pvww=TRUE; /由v到w的路径经过v和w两点 else strcpy(G.vexsv.routersw,-); srand(unsigned)time(NULL);/产生随机数种子，防止伪随机数 while(change=1) for(;bad20;)/连续20次随机交换无更新，为坏的交换，则停止随机交换 v=rand()%G.vexnum;w=rand()%G.vexnum;if(DvwINFINITY&v!=w) printf(%s节点向%s节点发送距离向量，,G.,G.); change=0; for(u=0;uG.vexnum;u+) if(DwuINFINITY&Dvw+DwuDvu)/从v经u到w的一条路径更短 Dvu=Dvw+Dwu;/更新最短距离 change=1; bad=0; /一有更新，则不是坏的交换 if(w!=u) strcpy(G.vexsv.routersu,G.);/记录上一跳节点名称 for(i=0;iG.vexnum;i+) Pvwi=Pvui|Puwi;/从v到w的路径经过从v到u和从u到w的所有路径 /if /for u if(change=1) stable+; printf( %s 的 路 由 表 如 下：n,G.); printf( 目的节点 最短路径 上一跳n);for(j=0;jG.vexnum;j+) printf( %8s %8d %8sn