软件基础课程设计-从某个源点到其余各顶点的最短路径

《软件基础课程设计-从某个源点到其余各顶点的最短路径》由会员分享，可在线阅读，更多相关《软件基础课程设计-从某个源点到其余各顶点的最短路径（23页珍藏版）》请在装配图网上搜索。

1、北京信息科技大学软件设计基础课程设计题 目： 从某个源点到其余各顶点的最短路径 学 院： 信息与通信工程学院 专 业： 通信工程专业 学生姓名： 班级/学号： 指导老师： 曹林 徐湛 杨玮 李振松 起止时间： 2013-9-22 至 2013-11-6 题目7从某个源点到其余各顶点的最短路径（难度系数9）主要内容1、 假设西安、北京、沈阳、武汉4个城市构成小型交通网，4个城市表示图的4个顶点，他们构成了无向连通图。以北京为源点，求北京到西安的最短路径；求北京到沈阳的最短路径；求北京到武汉的最短路径。2、 学会建立图的邻接表，理解图的基本概念。3、 学会编写DLL函数。4、 根据自己构建的连通图

2、，利用Dijkstra算法求从某个源点到其余各顶点的最短路径。5、 掌握C+编程环境的基本调试方法，熟练使用可视化C+编程工具。设计要求1、上交课程设计的书面材料，要求打印。包括课程设计任务书、主要内容，源程序，对程序的功能进行客观评价，明确指出自己编写了哪些具体函数。2、上交电子版源程序，包括邻接表建立程序、Dijkstra算法。3、自己编写一个求素数函数，把它书写成一个动态链接库形式，并在主函数中调用它。尝试把自己编写的程序写成动态链接库和静态链接库形式（无需上交），并比较以下三种EXE文件的大小。A：调用静态链接库生成的EXE执行文件。B：调用动态链接库生成的EXE执行文件。C：直接调用

3、函数生成的EXE执行文件。主要仪器设备计算机一台，安装Windows XP 操作系统、Microsoft Visual C+ 6.0、MSDN Library。主要参考文献1 侯俊杰. 深入浅出MFC(第二版)M. 武汉：华中科技大学出版社, 2001.2 谭浩强. C程序设计（第二版）M. 北京：清华大学出版社, 1999.3 孟彩霞. 计算机软件基础M. 陕西：西安电子科技大学出版社, 2003.4 严蔚敏, 吴伟民. 数据结构M. 北京：清华大学出版社, 2005.课程设计进度计划（起止时间、工作内容）选做最短路径题目的同学，2人1组，1人做Dijkstra算法，1人做Floyd算法，整

4、个课程设计共20学时，具体进度如下：4 学时 了解课题背景，选题，学习DLL，学习图的基本概念。4 学时 编写邻接表建立程序。4 学时 Dijkstra算法。4 学时 尝试利用Dijkstra算法求任意两个顶点之间的最小距离。4 学时 调试程序，答辩。课程设计开始日期2013-9-22课程设计完成日期2013-11-6课程设计实验室名称计算中心机房地 点健翔桥校区摘要 本次课程设计的问题：假设西安、北京、沈阳、武汉4个城市构成小型交通网，4个城市表示图的4个顶点，它们构成了无向连通图。以北京为源点，求北京到西安的最短路径；求北京到沈阳的最短路径；北京到武汉的最短路径。本次课程设计中应用Dijk

5、stra算法求最短路径。通过一个图的权值矩阵求出它的每两点间的最短路径矩阵，从图的带权邻接矩阵arcs(nn)开始，递归地进行n次更新，按一个公式，构造出矩阵S(1)，又用同样的公式由S(1)构造出S(2)最后又用同样的公式由S(n-1)构造出矩阵S(n)。矩阵S(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称S(n)为图的距离矩阵，同时还可引入一个后继节点矩阵pjk来记录两点间的最短路径。本次试验进行的是无向的计算，不同城市之间的距离由开始进行输入，最后显示两个城市之间的最短路径。目录任务书1摘要2目录3正文4一、应用迪科斯彻（Dijkstra）算法计算最短路径4二、Dijkst

6、ra 求最短路径的基本思想4三、Dijkstra 求最短路径的步骤4四、程序说明5五、功能实现5六、程序设计（二）12七、课程设计总结16参考文献17源代码18一、 应用迪科斯彻（Dijkstra）算法计算最短路径假设西安、北京、沈阳、武汉4个城市构成小型交通网，4个城市表示图的4个顶点，他们构成了无向连通图。以北京为源点，求北京到西安的最短路径；求北京到沈阳的最短路径；求北京到武汉的最短路径。这里路径指两顶点间的通路，路径的长度指所有经过的边的总长。“最短路径”的问题指当两个顶点间通路多于一条时，如何找出边长总和为最短的那条。Dijkstra提出按路径长度递增的次序求最短路径的方法。 二、

7、Dijkstra 求最短路径的基本思想把顶点分成两组，第一组是已确定最短路径的结点的集合，第二组是尚未确定最短路径的结点的集合。按路径长度递增的次序逐个把第二组的顶点放到第一组中。设求从v0到其它各顶点间的最短路径,则在任意时刻，从v0到第一组各顶点间的最短路径都不大于从v0到第二组各顶点间的最短路径。 三、 Dijkstra 求最短路径的步骤 设图以邻接矩阵arcs存储，矩阵中各元素的值为各边的权值。顶点到自身的权值用0表示，顶点间无边时其对应权值用-1表示。从顶点v0到其它各顶点间的最短路径的具体步骤如下： （1）初始化：第一组（集合s）只含顶点v0,第二组（集合v-s）含有图中其余顶点。

8、设一D向量，其下标是各顶点，元素值是顶点v0到各顶点的边的权值。若v0到某顶点无边，D向量中的对应值为-1。 （2）选D中最小的权值，将其顶点（j）加入s集合。 s=s j （3）修改从顶点v0到集合t(t=V-s)中各顶点的最短路径长度,如果 Dj+arcsjkDk 则修改Dk为 Dk=Dj+arcsjk (4) 重复（2）、（3）n-1次。由此求得v0到图上其余各顶点得最短路径。四、 程序说明为了编程方便，以V0代表北京，V1代表西安，V2代表沈阳，V3代表武汉。首先输入两点之间的距离，即为矩阵中各元素的值。顶点到自身的权值用0表示，顶点间无边时其对应权值用-1表示。五、 功能实现1）测试

9、1：假设：V0V1之间距离是5；V0V2之间距离是8；V0V3之间距离是9；V1V2之间距离是2；V1V3之间距离是3；V2V3之间距离是1。如图：9V3V2V1V031285图的邻接矩阵如下：运行程序： 运行程序出现如下界面，按照事先假设的数据输入。 、输入数据之后，程序给出所求的邻接矩阵、最短路径、最短距离。结果分析：根据程序的运行结果，我们可知： 、V0到V0的最短路径的距离为：0路径：V0 V0 、V0到V1的最短路径的距离为：5路径：V0 V1 、V0到V2的最短路径的距离为：7路径：V0 V1 V2 、V0到V3的最短路径的距离为：8路径：V0 V1 V32）测试2：假设：V0V1

10、之间不连通；V0V2之间不连通；V0V3之间距离是7；V1V2之间距离是2；V1V3之间距离是5；V2V3之间距离是2。如图：2V2V3V1V0257图的邻接矩阵如下：运行程序： 运行程序出现如下界面，按照事先假设的数据输入。 、输入数据之后，程序给出所求的邻接矩阵、最短路径、最短距离。结果分析：根据程序的运行结果，我们可知： 、V0到V0的最短路径的距离为：0路径：V0 V0 、V0到V1的最短路径的距离为：11路径：V0 V3 V2 V1 、V0到V2的最短路径的距离为：9路径：V0 V3 V2 、V0到V3的最短路径的距离为：7路径：V0 V33）测试3：假设：V0V1之间不连通；V0V

11、2之间距离是3；V0V3之间距离是9；V1V2之间距离是2；V1V3之间距离是3；V2V3之间不连通。如图：2V1V3V2V0339图的邻接矩阵如下：运行程序： 运行程序出现如下界面，按照事先假设的数据输入。 、输入数据之后，程序给出所求的邻接矩阵、最短路径、最短距离。结果分析：根据程序的运行结果，我们可知： 、V0到V0的最短路径的距离为：0路径：V0 V0 、V0到V1的最短路径的距离为：5路径：V0 V2 V1 、V0到V2的最短路径的距离为：3路径：V0 V2 、V0到V3的最短路径的距离为：8路径：V0 V2 V1 V3六、 程序设计（二）编写一个求素数函数，把它书写成一个动态链接库

12、形式，并在主函数中调用它。尝试把自己编写的程序写成动态链接库和静态链接库形式，并比较以下三种EXE文件的大小。A：调用静态链接库生成的EXE执行文件。B：调用动态链接库生成的EXE执行文件。C：直接调用函数生成的EXE执行文件。1）、动态连接、新建项目 “Win32 Dynamic-Link Library” 项目名称“sushu”,然后新建一个“sushu.cpp”文件，输入以下代码。动态连接DLL代码：、新建一个空的工程，项目名称“sushu”。然后新建一个“sushu.cpp”文件，文件代码如下。然后把刚才项目生成的 .lib、.dll文件拷贝到该工程的debug目录下。动态连接DLL调

13、用代码： 、运行结果：2）、静态连接、新建项目 “Win32 Dynamic-Link Library” 项目名称“sushu”,然后新建一个“sushu.h”文件，输入第一张图片代码。再新建一个“sushu.cpp”文件，输入第二张图片代码。静态连接DLL代码：、新建一个空的工程，项目名称“sushu”。然后新建一个“sushu.cpp”文件，文件代码如下。然后把刚才项目生成的 .lib、.dll文件拷贝到该工程的debug目录下。静态连接DLL调用代码：、运行结果：3）、结果分析静态链接库：lib中的指令被直接包含在最终生成的EXE文件中。动态链接库：dll不必被包含在最终的EXE中，EX

14、E文件执行时可以动态地引用和卸载DLL文件。 所以，调用静态链接库生成的EXE执行文件要比调用动态链接库生成的EXE执行文件大。七、 课程设计总结1、通过课程设计，我学会了如何建立图的邻接表，理解了图的基本概念。3、通过课程设计，我学会了如何编写DLL函数。4、能根据自己构建的连通图，利用Dijkstra算法求出从某个源点到其余各顶点的最短路径。5、掌握了C+编程环境的基本调试方法，能熟练的使用可视化C+编程工具。参考文献1 谭浩强. C程序设计（第二版）M. 北京：清华大学出版社, 1999.2 张青山. Dijkstra算法详细讲解M. 上海：复旦大学出版社, 2005.3 罗慧琴. VC

15、+动态链接库(DLL)编程深入浅出M. 陕西：西安电子科技大学出版社, 2003.4 严蔚敏, 吴伟民. 数据结构M. 北京：清华大学出版社, 2005./* 用邻接矩阵表示的图的Dijkstra算法的源程序*/#include #include #define Max INT_MAX#define MAXVEX 4#define FALSE 0#define TRUE 1typedef struct int num; /* 图的顶点个数 */ char vexsMAXVEX; /* 顶点信息 */ float arcsMAXVEXMAXVEX; /* 边信息 */Tu; /* 定义结构体Tu

16、类型 */void ShortestPath(Tu &G,int pMAXVEX,float D) int v,w,i,j; float min; int finalMAXVEX; /finalv为TRUE当且仅当vs,即已求得从v0到v的最短路径 for(i=0;iG.num;i+) finali=FALSE; Di=G.arcs0i; for(w=0;wG.num;w+) piw=FALSE; /*设空路径*/ if(Di!=-1) /*如果V0到Vi有直接路径则置pi0和pii为1*/ pi0=TRUE; pii=TRUE; /*for语句结束*/ final0=TRUE; /* 初始化

17、，表示顶点v0在集合S中 */ for(i=1;iG.num;i+) /*开始主循环，每次求得v0到某个v顶点的最短路径，并加v到s集*/ min=Max; /* 初始化，表示最短距离min的初始值为无穷大 */ for(w=0;wG.num;w+) /*在V-S中选出距离值最小顶点*/ if(!finalw&Dwmin)&(Dw!=-1) /*w顶点离v0顶点是更近*/ v=w; min=Dw; finalv=TRUE; /*离v0最近的v加入S集*/ for(w=0;wG.num;w+) /*更新当前最短路径及距离*/ if(G.arcsvw!=-1) /*假如v到w之间相通，则执行下一步

18、*/ if(!finalw&(min+G.arcsvwDw)|Dw=-1) /*修改Dw和pw，wv-S*/ Dw=min+G.arcsvw; /*修改路径长度*/ for(j=0;jG.num;j+)pwj=pvj; /*修改路径为经过v到达w*/ pww=TRUE; /*if结束*/ /*for结束*/*ShortestPath结束*/void main() printf(n*n);/*输出提示信息*/ printf( V0 代表 北京n); printf( V1 代表 西安n); printf( V2 代表 沈阳n); printf( V3 代表 武汉n); printf(*nn); i

19、nt i,j; Tu G; float DMAXVEX; /*D(v)为v0到v的路径长度*/ int pMAXVEXMAXVEX; /*p(v)记录v0到v的最短路径，若pvw为TRUE，则w是从v0到v当前求得最短路径上的顶点*/ G.num=4; /*一共有四个城市*/ for(i=0;iG.num;i+) /*for循环输入四个城市之间的距离*/ for(j=0;ji) printf( 请输入); printf(V%d,i); printf(到); printf(V%d,j); printf(的距离 (不通请输入-1)n ); scanf(%f,&G.arcsij); G.arcsji

20、=G.arcsij; /*该图为无向图，所以i到j的距离即为j到i的距离*/ /*if结束*/ /*else结束*/ /*for结束*/ /*for结束*/ ShortestPath(G,p,D); /*代入数据求解最短距离*/ printf(n以邻接矩阵的形式表示图为：n); /*以邻接矩阵形式输出图*/ for(i=0;iG.num;i+) for(j=0;jG.num;j+) printf(%12.0f,G.arcsij); printf(n); printf(nV0到其它各顶点的路径表示为：n); /*输出V0到其它各顶点的路径*/ for(i=0;iG.num;i+) for(j=0;jG.num;j+) printf(%12d,pij); printf(n); printf(nV0到其它各顶点的最短距离为：n); /*输出V0到其它各顶点的最短距离*/ for(i=0;iG.num;i+) printf( V0 到); printf( V%d ,i); printf(的最短路径的距离为：); printf(%.0fn,Di); printf(n n);/*主函数结束*/