《软件基础课程设计--从某个源点到其余各顶点的最短路径.doc》由会员分享，可在线阅读，更多相关《软件基础课程设计--从某个源点到其余各顶点的最短路径.doc（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课程设计实验室名称计算中心机房地 点健翔桥校区1摘要摘要 本次课程设计的问题：假设西安、北京、沈阳、武汉4个城市构成小型交通网，4个城市表示图的4个顶点，它们构成了无向连通图。以北京为源点，求北京到西安的最短路径；求北京到沈阳的最短路径；北京到武汉的最短路径。本次课程设计中
5、应用Dijkstra算法求最短路径。通过一个图的权值矩阵求出它的每两点间的最短路径矩阵，从图的带权邻接矩阵arcs(nn)开始，递归地进行n次更新，按一个公式，构造出矩阵S(1)，又用同样的公式由S(1)构造出S(2)最后又用同样的公式由S(n-1)构造出矩阵S(n)。矩阵S(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称S(n)为图的距离矩阵，同时还可引入一个后继节点矩阵pjk来记录两点间的最短路径。本次试验进行的是无向的计算，不同城市之间的距离由开始进行输入，最后显示两个城市之间的最短路径。2目录目录任务书1摘要2目录3正文4一、应用迪科斯彻（Dijkstra）算法计算最短路径
6、4二、Dijkstra 求最短路径的基本思想4三、Dijkstra 求最短路径的步骤4四、程序说明5五、功能实现5六、程序设计（二）12七、课程设计总结16参考文献17源代码1821正文从某个源点到其余各顶点的最短路径一、 应用迪科斯彻（Dijkstra）算法计算最短路径假设西安、北京、沈阳、武汉4个城市构成小型交通网，4个城市表示图的4个顶点，他们构成了无向连通图。以北京为源点，求北京到西安的最短路径；求北京到沈阳的最短路径；求北京到武汉的最短路径。这里路径指两顶点间的通路，路径的长度指所有经过的边的总长。“最短路径”的问题指当两个顶点间通路多于一条时，如何找出边长总和为最短的那条。Dijk
7、stra提出按路径长度递增的次序求最短路径的方法。 二、 Dijkstra 求最短路径的基本思想把顶点分成两组，第一组是已确定最短路径的结点的集合，第二组是尚未确定最短路径的结点的集合。按路径长度递增的次序逐个把第二组的顶点放到第一组中。设求从v0到其它各顶点间的最短路径,则在任意时刻，从v0到第一组各顶点间的最短路径都不大于从v0到第二组各顶点间的最短路径。 三、 Dijkstra 求最短路径的步骤 设图以邻接矩阵arcs存储，矩阵中各元素的值为各边的权值。顶点到自身的权值用0表示，顶点间无边时其对应权值用-1表示。从顶点v0到其它各顶点间的最短路径的具体步骤如下： （1）初始化：第一组（集
8、合s）只含顶点v0,第二组（集合v-s）含有图中其余顶点。设一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表示
9、，顶点间无边时其对应权值用-1表示。五、 功能实现1）测试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的最短路径的
10、距离为：8路径：V0 V1 V32）测试2：假设：V0V1之间不连通；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路
11、径：V0 V33）测试3：假设：V0V1之间不连通；V0V2之间距离是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调用代码： 、运行结果：2）、静态连接、新建项目 “Win32 Dynamic-Link Library” 项目名
