设计简单计算机网络结构用Dijktra算法求各终端的路由

设计简单计算机网络结构，用Dijktra算法求各终端的路由摘 要 本课程设计主要解决计算机网络中，路由器应该如何选择转发路径使得所经过的 路径最短。运用Dijktra算法求出一源点到其他所有节点的最短路径，主要特点是以起始点 为中心向外层层扩展，直到扩展到终点为止。并计算出最短路径的长度，以及该最短路径 的线路。课程设计及中，系统开发平台为Windows XP，程序设计语言为Visual C+6.0程 序运行平台为Windows 98/2000/XP。在程序设计中采用了邻接矩阵和镀铭数组相结合的方 法实现了对网络中结点和路径的存储和运算。程序通过调试运行，初步实现了设计目标， 经过调试和完善后，将可以运用在实际中解决问题。关键词 程序设计；计算机网络；Visual C+6.0； Dijkstra算法；最短路径目录1引言31.1课程设计背景31.2课程设计目的31.3课程设计内容32设计思路与方案52.1设计思路52.2设计方案52.3设计流程图53详细设计73.1程序函数作用的说明73.2建立有向带权值网图73.3求最短路径103.4打印结果124运彳丁结果154.1运行环境154.2系统测试155结束语17参考文献18附录191引言本课程设计主要解决计算机网络结构中路由器路径的选择，路由器路径的选择对于现 在计算机网络数据传输有着重要的作用。提高网络传输速度的关键是找到最佳路径， Dijkstra算法是找到最短路径的方法之一，运用Dijkstra算法找到最短路径，可以大大提高 网络的传输速度和网络的利用率。1.1课程设计背景计算机在我们的生活中扮演着越来越重的角色。我们的生活的因为计算机变得更精 彩。我们知道，21世纪是一个以网络为核心的信息时代。要实现信息化就必须依靠完善的 网络，因为网络可以非常迅速地传递信息。计算机网络，是指将地理位置不同的具有独立功能的多台计算机及其外部设备，通过 通信线路连接起来，在网络操作系统，网络管理软件及网络通信协议的管理和协议下，实 现资源和信息传递的计算机系统。路由器将不同网络连接起来，另外，路由器是信息选择 传送的路线。选择通畅快捷的近路，能发发提高通信速度，减轻网络系统通信负荷，节约 网络系统资源，提高网络系统畅通率。从而让网络系统挥发出更大的效益出来。路由的主 要工作是经过路由器的每个数据帧寻找一条最佳传输路径，并将数据有效地传送到目的站 点，由此可见，选择最佳路径的策略既路由算法是路由器的关键所在。用Dijikstra算法求出各终端路由到各路由的最短路径。模拟一个有向网中源点到其他 节点的最短路径和距离，并求出所经过的路径的顶点。设计的只要目的是找到网中两点的 最短路径，这样在计算机实际运用中可以使得数据在网络中的传输更加快捷，有保证，有 高效，同时也有利于提高数据的传输量。所以，我们想要提高网络的传送速度和效率，最主要的是找到最佳路由选择实现方法， 路径选择算法的好坏直接决定着网络性能的高低以及网络资源的利用率，而各种路由选择 算法的目标都是使网络延迟最小，吞吐量最大，经过的节点数最少，这些问题其实归结起 来就是最短路径问题。1.2课程设计目的在程序设计中关键是如何将路由器的工作原理用数据结构联系起来，转为用邻接矩 阵，数组，字符串，Dijkstra算法等C+语言知识设计出程序。通过程序的编写，调试和 运行可以进一步掌握数据结构计算的实现的基本方法。更进一步理解网络图的表示方法，熟悉将Dijkstra算法运用于实际应用中。与此同时很大程度上培养自我完成程序设计和解 决难点的能力。1.3程序设计内容本课程设计是用邻接矩阵完成图的表示和路径以及长度的求解。对邻接矩阵arcnm 中的每一个元素只能有三种情况：1.当n=m时，pnm=0； 2.当顶点n到m无边时， Gnm=MAX； 3.当顶点n到m有边并且权值为Gnm时，pnm=Gnm。建立图的 表示模块，在建立图之后从单源点开始求最短路径，并显示出来。程序的功能模块：终端路由的求解程序网图数据的初始化求 出 最 短 的 路 径计 算 各 路 径 的 长 度打印结果图1.1程序的功能模块2设计思路与方案2.1设计思路在网图中，任意两个顶点之间都可能存在边，并且两点之间可达的路径可能不是唯一 的，不同的路径所经过的路径值的大小不一样，为了减小到达点之间的距离，我们就需要 找到两点之间的最短路径。在网图中，任意两顶点都可能存在边，但是无法通过顶点的存取位置反映顶点之间的 邻接关系，因此图没有顺序存储结构，所以图的存取需要借助邻接矩阵或邻接表来存储。 图的邻接矩阵是一个n*n的矩阵，所以其空间代价是O(n*n)。它的存储空间只与它的顶 点数有关，与边数无关。适用与边稠密的图。邻接表的空间代价与图的边数及顶点数有关， 每个顶点在顶点表中都要占据一个数据元素的位置(既使该顶点没有邻接表)，且每条边 必须出现在某个顶点的边表中，所以邻接表的空间代价是O(n+e)，适用于稀疏的图中。 因为本课程设计用于计算机网络结构查找路由的最短路径，是稀疏的图的可能性比较小， 所以本课程设计选择邻接矩阵存储图的信息。通过使用邻接矩阵存储图的信息，再通过Dijkstra算法求出最短路径。2.2设计方案第一步，将一个有向带权的网图的基本信息存储到邻接矩阵中，用InitMatrix()函数初 始化矩阵，再利用GreateMatrix()输入有向带权值的图的信息。再用PrintMatrix()函数输出 输入的矩阵。第二步，通过Dijkstra算法，并以数组为辅，求解最短路径，最短路径所经过的每个 顶点。第三步，打印出Dijkstra算法求出的最短路径的信息。2.3设计流程图：图2.1总设计流程图3详细设计3.1程序函数的作用说明函数声明功能声明void InitMatrix()初始化邻接矩阵表示的有向带权值图void GreateMatrix(0建立邻接矩阵表示的有向带权值图（既通过输入图的每条边建立图的邻接矩阵）void PrintMatrix()输出邻接矩阵表示的有向带权值图（既用邻接矩阵体现出输入的图的信息）void Path()辅助函数viod Dijkstra()用Dijkstra算法求最短路径viod PrintPath()输出从源点到每个顶点最短路劲及长度的函数3.2建立有向带权值网图输入数据，以初始化矩阵。图3.1有向图流程图:图3.2输入流程图输入数据的核心代码：void CreateMatrix(adjmatrix G)int i, j, x;/分别表示起点，终点，权值cout 请输入顶点信(顶点是以0为第一个顶点，依次对应下去)n起点终点权值(输入 -1结束顶点的输入) i j x;while(i != -1)/遇到-1，输入完-1和j,x的值循环结束Gij = x;cin i j x;初始化后的邻接矩阵Inf10Inf30100Inf050InfInfG55InfInf0Inf10（注：Inf表示Vi不能到达Vj）InfInf20060InfInfInfInf0输出流程图:图3.3输出矩阵流程图输出邻接矩阵主要代码如下：void PrintMatrix(adjmatrix G, int n)int i, j；for(i = 0; i n; i+)for(j = 0; j n; j+)if(Gij = MaxValuey/如果权值为最大值输出Inf,否则输出对应的权值大小 cout setiosflags(ios:left) setw(5) Inf;else cout setiosflags(ios:left) setw(5) Gij;cout endl;3.3求最短路径求最短路径流程图：图3.4 Dijkstra算法流程图用Dijkstra算法求解路径到各终端路由，是本程序的核心部分。核心函数如下:void Dijkstra(adjmatrix GA, int dist, edgenode *path, int i, int n)int j, k, w, m;bool * s = new booln; /bool 型数组for(j = 0; j n; j+)if(j = i)sj = true;elsesj = false;distj = GAij;初始点到初始点设置为trueif(distj adjvex = i;p2-adjvex = j;p2-next = NULL;p1-next = p2;pathj = pl;elsepathj = NULL;for(k = 1; k = n-2; k+)做调整，找出最短路径断点调试w = MaxValue;m = i;for(j = 0; j n; j+)if(sj = false & distj w)w = distj;m = j;if(m != i)sm = true;elsebreak;for(j = 0; j n; j+)用现找点作为初始点进一步对所有点进行调整if(sj = false & distm + GAmj distj)distj = distm+GAmj;Path(path, m, j);delete s;3.4打印结果流程图：图3.5打印流程图此函数是最后查找到结果的输出，核心代码如下：void PrintPath(int dist, edgenode * path, int i, int n)int j；for(j = 0; j n; j+)if(i != j)cout 顶点v i ”到顶点v j ”的最短路径的长度为 distj ,最短路径为：;edgenode * p = pathj;while(p != NULL)cout setw(4) adjvex;p = p-next;cout endl;4系统运行环境与测试4.1运行环境程序的运行环在本课程设计中，系统开发平台为WindowsXP，程序设计语言为C+,境为 VisualC+6.0。4.2系统测试（1）输入顶点数请输入的有向带权图的顶点个数二5图4.1输入定点个数（2）输入顶点的信息:尔输入的有向带权图的邻接矩阵表示为二图4.2输入顶点信息（3）用邻接矩阵的形式输出有向带权值网图你输入的有向带权图的邻接矩阵表示为:Inf30Inf9020InfInf40InfInfInfInfInf15InfInfInfInfInfInfInfInf3545Inf请输入你要输入的源点和标记量的值如果标记值为结束程序”图4.3用邻接矩阵的形式输出有向带权值网图（4）输入要查询的源点值并且输出结果14 4 40 0 0 00 5 5 03 5 6 2 为为为为 度度度度为为为为 H HTKnTKnTKnTK -S-S-S-S- +K+K+K+K 曰-取为为2为 X工至:X工 ,/11/11勺-1/11 nTKnTK.nTK 圭车口圭. 曰W取就最+K 0,0,曰取0,至至至至 1111 1割割 1顶顶顶顶至至至至 0 0 0 0 顶顶顶顶0 0 5 0 i i i i 为为为为 度度度度 -fe-fe-fe-fe ii nrnTnTnT 豆豆豆豆 曰-取 0 13 4 gggg 2 2 2 2 1割割 2顶顶顶顶为i为 径机机径 _口习.-.习.-_口 nTKXxnTK 一 口手专.一 !- -H-口丸口-H. 最就就最 +K+K 0,曰|11 取0, 0 0 0 r 0 0 0 5 0 14 5 1 为为为为 度度度度nTKnTKnTKnTK一9一一9一一七一一七_BiU0U2U3U4nrnTnTnT一日一一日一一日一一日_USU1U2U3U4为为为为 H HTKnTKnTKnTK -S-S-S-R- A.A.A.A.为为为为 -fe-fe-fe-fe 的的的的 18 HTKHTKnTKnTK -S-S-S-R- A.A.A.A. 曰雨 0 12 4占罟罟罟gSS3 3 3 31占苫苫苫g3顶顶顶顶为为： 岌口Ktc.wx, 一口I.一一口|._.-:-12.-:-12 -A.-A.:-:n:-:nA.A. 0,0,曰馨取 0 0 0 0 5 5 113 4为为为为 度度度度 -fe-fe-fe-fe 的的的的 is HTKHTKnTKnTK -R-R-R-R- A.A.A.A. 曰阪 0 12 3占苫苫苫g SS 4顶顶顶顶Press Any key to continue图4.3查询各点到其他点的最短路径5结束语本课程设计的内容为设计一个简单的计算机网络结构，利用Dijkstra算法求出远点到 个顶点的最短路径，用邻接矩阵作为辅助工具来表示有向带权值图，设计出一个了简单的 模拟路由工作过程的程序。通过这两周的课程设计的学习，我学到了很多东西，我更加了解了迪杰斯特拉算法的 意义，能够更好地掌握Dijkstra算法，同时检验了我所学的知识，也培养了我如何很够很 好的独自完成一件事情。在课程设计过程中，我们学会了要尽力独自完成设计，这样能够 让我们能够更快，更好的提升我们的能力。课程设计是我们专业课程知识的综合应用的实践，是我们迈向社会，从事职业前一 个必不可少的过程。在本课程设计中，不仅用到了数据结构的知识，还用到了计算机网络 的知识，这样就把我们所学的专业知识联系到一起。通过这次课程设计我明白了理论与实 际相结合，和其他课程相结合的重要性。掌握了好的理论并不一定能够很好的运用到自己 的程序中，我们只要通过不断学习和实践，不断的运用，才能真正地掌握所学的知识。通过本次的课程设计，我巩固和温习了 C语言和C+语言，还学习了其他的知识如：写文档的时候，规格的概念，层次布局以及逻辑结构也有了更清晰的认识等等。在这次设 计过程中，体现出了单独设计模具的能力以及综合运用知识能力，体会了学以致用，突出 自己劳动成果的喜悦心情，从中发现自己平时学习的不足和薄弱环节，从而加以弥补。参考文献1 王红梅，胡明，王涛，数据结构（C+）北京：清华大学出版社，20072 王红梅，胡明，王涛，数据结构（C+）学习辅导与实验指导北京：清华大学出版社20073 严蔚敏，吴伟明，数据结构（C语言版）清华大学出版社，19974 谭浩强C+程序设计（第一版）北京：清华大学出版社2004.65 谭浩强C程序设计（第三版）北京：清华大学出版社，2005附录：课程设计源程序程序名称：求最短路径.CPP程序功能：采用Dijkstra算法设计程序，找到路由的最短路径程序作者：最后修改日期：2012-7-3#include #include using namespace std;#define MaxVerNum 20#define MaxValue 10000typedef int adjmatrixMaxVerNumMaxVerNum;邻接矩阵的类型定义typedef struct Nodeint adjvex;/ 权值struct Node * next;/弧信息的指针edgenode;指针数组path基类型定义初始化邻接矩阵表示的有向带权图void InitMatrix(adjmatrix G)int i, j;for(i = 0; i MaxVerNum; i+)for(j = 0; j MaxVerNum; j+)Gij = MaxValue; /初始化所有点到点的权值为最大值建立邻接矩阵表示的有权带向图(即通过输入图的每条边建立图的邻接矩阵)void CreateMatrix(adjmatrix G)inti, j, x;/分别表示起点，终点，权值cout 请输入顶点信(顶点是以0为第一个顶点，依次对应下去)n起点终点权值(输入 -1结束顶点的输入) i j x;while(i != -1)/遇到-1,输入完-1和j,x的值循环结束Gij = x;cin i j x;输出邻接矩阵表示的有向带权图(即输出图的每条边)void PrintMatrix(adjmatrix G, int n)int i, j;for(i = 0; i n; i+)for(j = 0; j n; j+)if(Gij = MaxValue)/如果权值为最大值输出Inf,否则输出对应的权值大小 cout setiosflags(ios:left) setw(5) Inf;elsecout setiosflags(ios:left) setw(5) Gij;cout next;delete p;p = pathj;p = pathm;while(p != NULL)q = new edgenode;q-adjvex = p-adjvex;if(pathj = NULL)pathj = q;elses-next = q;s = q;p = p-next;q = new edgenode;q-adjvex = j;q-next = NULL;s-next = q;求最短路径的Dijkstral算法void Dijkstra(adjmatrix GA, int dist, edgenode *path, int i, int n)int j, k, w, m;bool * s = new booln; /bool 型数组for(j = 0; j n; j+)if(j = i)sj = true;elsesj = false;distj = GAij;初始点到初始点设置为trueif(distj adjvex = i;p2-adjvex = j;p2-next = NULL;p1-next = p2;pathj = p1;elsepathj = NULL;for(k = 1; k = n-2; k+)做调整，找出最短路径断点调试w = MaxValue;m = i;for(j = 0; j n; j+)if(sj = false & distj w)w = distj;m = j;if(m != i)sm = true;elsebreak;for(j = 0; j n; j+)用现找点作为初始点进一步对所有点进行调整if(sj = false & distm + GAmj distj)distj = distm+GAmj;Path(path, m, j);delete s;输出从源点到每个顶点的最短路径及长度的函数void PrintPath(int dist, edgenode * path, int i, int n)int j;for(j = 0; j n; j+)if(i != j)cout 顶点v i ”到顶点v j ”的最短路径的长度为 distj ,最短路径为：;edgenode * p = pathj;while(p != NULL)cout setw(4) adjvex;p = p-next;cout endl;void main()int i, n,j;cout n;adjmatrix g;/顶一个一个矩阵 gInitMatrix(g);/初始化矩阵 gCreateMatrix(g);/对矩阵 g 赋值cout 你输入的有向带权图的邻接矩阵表示为： endl;PrintMatrix(g, n);/ 输出矩阵int * d = new int n; /new出来n维的整形数组edgenode * path = new edgenode * n; / 指向指针的数组while(j!=0)cout ij;Dijkstra(g, d, path, i, n);PrintPath(d, path, i, n);coutn;