1、 软件软件设计设计基础课程设计基础课程设计 题题 目：目： 从某个源点到其余各顶点的最短路径从某个源点到其余各顶点的最短路径 学学 院：院： 信息与通信工程学院信息与通信工程学院 专专 业：业： 通信工程专业通信工程专业 学生姓名：学生姓名： 班级班级/学号学号： 指导老师：指导老师： 起止起止时间：时间： 2013-9-22 至至 2013-11-6 任务书 1 题目题目 7 从某个源点到其余各顶点的最短路径（难度系数 9） 主要主要 内容内容 1、 假设西安、北京、沈阳、武汉 4 个城市构成小型交通网，4 个城市表示图的 4 个顶 点，他们构成了无向连通图。以北京为源点，求北京到西安的最短
2、路径；求北京到 沈阳的最短路径；求北京到武汉的最短路径。 2、 学会建立图的邻接表，理解图的基本概念。 3、 学会编写 DLL 函数。 4、 根据自己构建的连通图， 利用 Dijkstra 算法求从某个源点到其余各顶点的最短路径。 5、 掌握 C+编程环境的基本调试方法，熟练使用可视化 C+编程工具。 设计设计 要求要求 1、上交课程设计的书面材料，要求打印。包括课程设计任务书、主要内容，源程序， 对程序的功能进行客观评价，明确指出自己编写了哪些具体函数。 2、上交电子版源程序，包括邻接表建立程序、Dijkstra 算法。 3、自己编写一个求素数函数，把它书写成一个动态链接库形式，并在主函数中
3、调用 它。尝试把自己编写的程序写成动态链接库和静态链接库形式（无需上交） ，并比 较以下三种 EXE 文件的大小。 A：调用静态链接库生成的 EXE 执行文件。 B：调用动态链接库生成的 EXE 执行文件。 C：直接调用函数生成的 EXE 执行文件。 主要主要 仪器仪器 设备设备 计算机一台，安装 Windows XP 操作系统、Microsoft Visual C+ 6.0、MSDN Library。 主要主要 参考参考 文献文献 1 侯俊杰. 深入浅出 MFC(第二版)M. 武汉：华中科技大学出版社, 2001. 2 谭浩强. C 程序设计（第二版）M. 北京：清华大学出版社, 1999
4、3 孟彩霞. 计算机软件基础M. 陕西：西安电子科技大学出版社, 2003. 4 严蔚敏, 吴伟民. 数据结构M. 北京：清华大学出版社, 2005. 课程设计进度计划（起止时间、工作内容）课程设计进度计划（起止时间、工作内容） 选做最短路径题目的同学，2 人 1 组，1 人做 Dijkstra 算法，1 人做 Floyd 算法，整个课程设 计共 20 学时，具体进度如下： 4 学时 了解课题背景，选题，学习 DLL，学习图的基本概念。 4 学时 编写邻接表建立程序。 4 学时 Dijkstra 算法。 4 学时 尝试利用 Dijkstra 算法求任意两个顶点之间的最小距离。 4 学时 调试程
5、序，答辩。 课程设计开始日期课程设计开始日期 2013-9-22 课程设计完成日期课程设计完成日期 2013-11-6 课程设计实验室名称课程设计实验室名称 计算中心机房 地地 点点 摘要 2 摘要摘要 本次课程设计的问题：假设西安、北京、沈阳、武汉 4 个城市构成小型交通 网，4 个城市表示图的 4 个顶点，它们构成了无向连通图。以北京为源点，求北京 到西安的最短路径；求北京到沈阳的最短路径；北京到武汉的最短路径。 本次课程设计中应用 Dijkstra 算法求最短路径。通过一个图的权值矩阵求出 它的每两点间的最短路径矩阵，从图的带权邻接矩阵 arcs(nn)开始，递归地进 行 n 次更新， 按一个公式， 构造出矩阵 S(1)， 又用同样的公式由 S(1)构造出 S(2) 最后又用同样的公式由 S(n-1)构造出矩阵 S(n)。矩阵 S(n)的 i 行 j 列元素便是 i 号顶点到 j 号顶点的最短路径长度，称 S(n)为图的距离矩阵，同时还可引入一个 后继节点矩阵 pjk来记录两点间的最短路径。 本次试验进行的是无向的计算，不同城市之间的距离由开始进行输入，最后 显示两个城市之间的最短路径。 目录 3 目录目录 任务书任务书
