《编程验证最短路径路由算法》由会员分享，可在线阅读，更多相关《编程验证最短路径路由算法（13页珍藏版）》请在金锄头文库上搜索。
1、编程验证最短路径路由算法摘要：在在一个带权图中，从某一个单源节点，走到其他节点，如何求得所有路径中的最短 路径，是单元节点最短路径问题。而在路由算法中，与此类似，可以抽象出该模型来。迪杰 斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959年提出的。是从一个顶点到其余各顶 点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点 为中心向外层层扩展，直到扩展到终点为止。本文在迪杰斯特拉算法的基础上，通过C语言 程序，构建一个无向带权图，以程序的方式来验证最短路径路由算法。关键词：最短路劲；路由算法；程序验证1迪杰斯特拉算法原理简介Dijikstra算法是典型的求单源节点到
2、其他节点的最短路径算法。其基本思想是，通过构 建一个节点之间的邻接矩阵来表示节点之间的路径长度。假设我们需要求得是节点v到其他 节点的最短路径，在最开始初始化v到其他节点的距离，当v与其他节点之间存在路径的时 候，即将该节点之间的路径长度赋为该路径长度的权值，如果V到某个节点之间不存在直接 路径，则将V到该节点的权值赋为无穷大（在程序中使用一个较大的数值来代表无穷大）。图1：无向带权图图1对应的邻接矩阵为：V0V1v2v3v4V00208810V1200689V286038V388305V4109850算法的基本思想是按照路径长度的增长来通过迭代，依次求得V0节点到其他节点的路 径长度，当经过
3、n次迭代后，即可求出V0到其他n-1个节点之间的最短路径长度。首先将 节点分为两个集合S1和S2,其中S1初始只包含V0节点，S2初始为其他节点，然后算法按 照以下规则来迭代：（1）从集合S2中选择一个节点Vi使其到V0节点之间的距离最短，并把Vi加入到、1 集合中；（2）用Vi作为中间节点来过渡，判断是否能通过Vi节点作为中间节点，使得从V0到 S2集合中其他的节点路径更短，如果通过Vi作为中间节点的过渡得到的距离更短，即更新 V0到S2中节点之间的距离权值；(3) 重复(1) - (2)的迭代过程，知道S2集合中不再有节点为止。2 C语言程序验证最短路径路由算法在程序中采用C语言程序来验证
4、最短路径算法，分别验证了单源节点到其它节点的最短 路径迪杰斯特拉算法和每对节点间的最短路径Floyd算法。在该程序中将数据的输入和输出 放在文件中进行。以下是程序数据输入文件数据：J data.txt- Notepad . I 口 I 回Fife Edit Format View Helpn=6edge=10(0,1) 20 (0,2) 15 (1,0) 2 (1,5) 30 (1,4) 10 (2,1) 4 (2,5) 10 (4,3) 15 (5,3) 4 (5,4) 10图2程序数据输入文件程序数据输入文件用来描述构建的无向带权图，口n=6代表有6个节点，edge=10代表 图中有10条
5、边，下面十对()中间的数据分别描述了路径的起始节点后终端节点，括号后 面的数字代表该条路径的权值。程序中设计到的几个主要函数、参数的交代(该部分在程序源代码中也通过注释的形式 标明)：#define ok 0 :定义函数的返回值#define eror 1 :定义函数的返回值#define maxOfInt 99999 :定义最大的路径长度int read_data(int *a,int *n);:从文件中读数据的函数int ShortestPath_Floyd(int n,int *p,int *D); : Floyd 算法函数int ShortestPat_dijkstra(int *D,
6、int *DG,int v0,int *p,int vexnum)： Dijkstra 算法函数；int draw_path(FILE *fp,int *p,int v0,int len); /after each time call functions of dijkstra,get the path from p matrix.:生成最短路径上的节点顺序的函数。3程序运行结果图3程序输出窗口程序输出窗口只会输出提示程序是否运行正常的相关信息，而程序的结果将分别输出到 三个txt文本中。下面分别展示：j dlijkstra_outputl.txt - NotepadFile Edit For
7、mat View Help|the shortest 1 ength of vO to other vertex:00000000000图4 Dijkstra算法输出结果1图4展示的是，最初从v0节点到其它节点的路径长度，从图中可以看出有很多节点在 最初是不可达的，这将与下面的第二个输出结果图对比。j d jjkstra_output2.trt - NotepadFile Edit Format View Helpthe shortest 1ength of both vertex:333033pathbetweenvertex 0 to1：0 1pathbetweenvertex 0 to2
8、：0 2pathbetweenvertex 0 to3：0 3pathbetweenvertex 0 to4:0 4pathbetween 0vertex 0 to175:250 51027图5-1 Dijkstra算法输出结果图2003403pathbetweenvertex3 to 0:5 4 2 1 0pathbetweenvertex3 to 1:5 1pathbetweenvertex3 to 2:5 2pathbetweenvertex3 to 4:5 4图5 -2 Dijkstra算法输出结果图2在该图中，分别找到了从v0节点到其它节点之间的路径是怎样的。此处只是部分输出 图，在
9、该程序中，运行验证了从其它节点出发的，最短路径。the imtai length of both vertexwww10ww0co150410of bothvertex292925101414000150410path between vertex path between vertex path between vertex path between vertex path between vertex path between vertex path between vertex path between vertex path between vertex path between ve
10、rtex path between vertex path between vertex path between vertex path between vertex path between vertex path between vertex path between vertex path between vertex0 to0 to0 to0 to0 to1 to1 to1 to1 to1 to2 to2 to2 to2 to2 to4 to5 to5 to1234502345013453 4 51 5 15 2 3 2 o 3 422222004401151500000111112
11、2222floyd_autputl.txt - NotepadFile Edit Format View Help0201520w40000000000000000000 the shortest 1ength019152017640000000000000000000图6 Floyd算法输出结果图在图6中展示了调用Floyd算前和调用之后的最短路径矩阵的变化，明显第二个矩阵相 比第一个矩阵，为无穷远的元素要少，而且相对应位置的值也要小。4程序源代码#include#include#include#define ok 0#define eror 1#define maxOfInt 99999i
12、nt read_data(int *a,int *n);int ShortestPath_Floyd(int n,int *p,int *D);int ShortestPat_dijkstra(int *D,int *DG,int v0,int *p,int vexnum);int draw_path(FILE *fp,int *p,int v0,int len); /after each time call functions of dijkstra,get the path from p matrix.int main()FILE *fpf=NULL,*fp=NULL;int *D,n,*
13、p,i,j,k,tempj,flag=0,* path,path_len, *pd,* mind;/*Floyd algorithms area*read_data(&D,&n);if( (fpf = fopen( floyd_output1.txt, w ) = NULL )printf( The file floyd_output1.txt was not openedn);return eror;elseprintf( The file floyd_output1.txt was openedn);p=(int *)malloc(n*sizeof(int *);path=(int *)m
14、alloc(n*sizeof(int);for(i=0;in;+i)pi=(int *)malloc(n*sizeof(int *);for(j=0;jn;+j)pij=(int *)malloc(n*sizeof(int);fprintf(fpf,the inital length of both vertexn);for(i=0;in;+i)for(j=0;jn;+j)if(Dij=maxOfInt)fprintf(fpf,8t);elsefprintf(fpf,%dt,Dij);fprintf(fpf,n);ShortestPath_Floyd(n,p,D);fprintf(fpf,nthe shortest length of both vertexn);for(i=0;in;+i)for(j=0;jn;+j)if(Dij
