单源结点最短路径问题设计书.doc

《单源结点最短路径问题设计书.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、单源结点最短路径问题设计书1设计容单元结点最短路径问题。问题描述：求从有向图中的某一结点出发到其余各结点的最短路径。基本要求：（1）有向图采用邻接矩阵表示。（2）单元结点最短路径问题采用狄克斯特拉算法。（3）输出有向图中从源结点到其余各结点的最短路径和最短路径值。测试数据：如下图有向带权图所示2算法思想描述狄克斯特拉算法思想：设置两个顶点的集合S和T，集合S中存放已找到最短路径的顶点，集合T中存放当前还未找到路径的顶点。初始状态时，集合S中包含源点，设为v0，然后从集合T中选择v0路径长度最短的顶点u加入到集合S

2、中，集合S中每加入一个新的顶点u，都要修改源点v0到集合T中剩余顶点的当前最短路径的当前最短路径长度值，集合T中各顶点的新的当前最短路径长度值为原来的当前最短路径长度值与从源点过顶点u到达该顶点的路径长度中的较小者。此过程不断重复，直到集合T中的顶点全部加入到集合S中为止。3算法及程序实现#include#includetypedefcharDataType;//定义顺序表的数据类型为char#defineMaxSize10//定义顺序表数组的最大个数#defineMaxVe

3、rtices10//定义顶点的最大个数#defineMaxWeight10000//定义权值的具体最大值#include"AdjMGraph.h"//包含AdjMGraph.h头文件#include"AdjMGraphCreate.h"//包含AdjMGraphCreate.h头文件#include"Dijkstra.h"//包含Dijkstra.h函数的文件voidmain(void){AdjMGraphg;chara[]={'A','B','C','D','E','F'};RowColWeightrcw[]=

4、{{0,1,10},{0,2,12},{1,3,16},{1,4,25},{2,0,4},{2,1,3},{2,3,12},{2,5,8},{3,4,7},{5,3,2},{5,4,10}};inti,n=6,e=11;intdistance[6],path[6];CreatGraph(&g,a,n,rcw,e);Dijkstra(g,0,distance,path);printf("t从顶点%c到其余各顶点的最短路径值分别为:",g.Vertices.list[0]);for(i=1;i

5、printf("t%c到%c的最短路径值为:%d",g.Vertices.list[0],g.Vertices.list[i],distance[i]);printf("t从顶点%c到其余各顶点的最短路径的前一顶点为:",g.Vertices.list[0]);for(i=1;i

6、h[i]]);}4算法测试及结果从程序的运行结果，再结合测试数据的有向带权图，可以得出，从顶点A到其余各顶点的最短路径及距离如下。A到B：最短路径为（A，B），其距离为10A到C：最短路径为（A，C），其距离为12A到D：最短路径为（A，C，F，D），其距离为22A到E：最短路径为（A，C，F，D，E），其距离为29A到F：最短路径为（A,C,F）,其距离为205总结课程设计对学生而言是其对所学课程容掌握情况的一次自我验证，从而有着极其重要的意义。通过课程设计能提高学生对所学知识的综合应用能力，能全面检查并掌握所

7、学容；《数据结构》从课程性质上讲是一门专业基础课，它的目的和任务就是训练学生对计算机加工的数据对象进行分析的能力，选择适当的数据结构及相应算法的能力，训练学生的编码以及调试能力，进而增加其对学习和应用相关专业课的兴趣。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，将结论用于实践，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中当然遇到了问题，可以说得是困难重重，毕竟这是不可避免的，同时在设计的过程中发现了自己的不足

8、之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。由于编程水平有限，其中头文件和狄杰斯特拉算法的函数设计等是参考书上资料，我想在以后的学习中，要更注重实践这一环节。在设计的过程中遇到种种问题，同时在设计的过程中发现了自己的不足之处，对一些前面学过的知识理解得不够深刻，掌握得不够牢固，通过这次课程设计之后，我们把前面所学过的知识又重新温故了一遍。从设计过程看，在整整半