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

《软件基础课程设计--从某个源点到其余各顶点的最短路径》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

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

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

5、汉的最短路径。本次课程设计中应用Dijkstra算法求最短路径。通过一个图的权值矩阵求出它的每两点间的最短路径矩阵，从图的带权邻接矩阵arcs(n×n)开始，递归地进行n次更新，按一个公式，构造出矩阵S(1)，又用同样的公式由S(1)构造出S(2)…最后又用同样的公式由S(n-1)构造出矩阵S(n)。矩阵S(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称S(n)为图的距离矩阵，同时还可引入一个后继节点矩阵p[j][k]来记录两点间的最短路径。本次试验进行的是无向的计算，不同城市之间的距离由开始进行输入，最后显示两个城市之间的最短路径。77目录目录任务书1摘要

6、2目录3正文4一、应用迪科斯彻（Dijkstra）算法计算最短路径4二、Dijkstra求最短路径的基本思想4三、Dijkstra求最短路径的步骤4四、程序说明5五、功能实现5六、程序设计（二）12七、课程设计总结16参考文献17源代码1897正文—从某个源点到其余各顶点的最短路径一、应用迪科斯彻（Dijkstra）算法计算最短路径假设西安、北京、沈阳、武汉4个城市构成小型交通网，4个城市表示图的4个顶点，他们构成了无向连通图。以北京为源点，求北京到西安的最短路径；求北京到沈阳的最短路径；求北京到武汉的最短路径。这里路径指两顶点间的通路，路径的长度指所有经过的边的总长。

7、“最短路径”的问题指当两个顶点间通路多于一条时，如何找出边长总和为最短的那条。Dijkstra提出按路径长度递增的次序求最短路径的方法。二、Dijkstra求最短路径的基本思想把顶点分成两组，第一组是已确定最短路径的结点的集合，第二组是尚未确定最短路径的结点的集合。按路径长度递增的次序逐个把第二组的顶点放到第一组中。设求从v0到其它各顶点间的最短路径,则在任意时刻，从v0到第一组各顶点间的最短路径都不大于从v0到第二组各顶点间的最短路径。三、Dijkstra求最短路径的步骤设图以邻接矩阵arcs存储，矩阵中各元素的值为各边的权值。顶点到自