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

北京信息科技大学 软件设计基础课程设计 题 目： 从某个源点到其余各顶点的最短路径 学 院： 信息与通信工程学院 专 业： 通信工程专业 学生姓名： 班级/学号： 指导老师： 曹林 徐湛 杨玮 李振松 起止时间： 2013-9-22 至 2013-11-6  题目 从某个源点到其余各顶点的最短路径（难度系数9） 主要 内容 设计 要求 主要 仪器 设备 Windows XP 操作系统、Microsoft Visual C++ 6.0、MSDN Library。 主要 参考 文献 侯俊杰. 深入浅出MFC(第二版)[M]. 武汉：华中科技大学出版社, 2001. 北京出版社, .. [3] 孟彩霞. 计算机软件基础[M]. 陕西：西安电子科技大学出版社, 2003. [4] 严蔚敏, 吴伟民. 数据结构[M]. 北京：清华大学出版社, 2005. 课程设计进度计划（起止时间、工作内容） 课程设计开始日期 2013-9-22 课程设计完成日期 2013-11-6 课程设计实验室名称 地 点 摘要 本次课程设计的问题：假设西安、北京、沈阳、武汉4个城市构成小型交通网，4个城市表示图的4个顶点，它们构成了无向连通图。以北京为源点，求北京到西安的最短路径；求北京到沈阳的最短路径；北京到武汉的最短路径。 本次课程设计中应用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]来记录两点间的最短路径。 本次试验进行的是无向的计算，不同城市之间的距离由开始进行输入，最后显示两个城市之间的最短路径。 目录 任务书 1 摘要 2 目录 3 正文 4 一、应用迪科斯彻（Dijkstra）算法计算最短路径 4 二、Dijkstra 求最短路径的基本思想 4 三、Dijkstra 求最短路径的步骤 4 四、程序说明 5 五、功能实现 5 六、程序设计（二） 12 七、课程设计总结 16 参考文献 17 源代码 18 应用迪科斯彻（Dijkstra）算法计算最短路径 假设西安、北京、沈阳、武汉4个城市构成小型交通网，4个城市表示图的4个顶点，他们构成了无向连通图。以北京为源点，求北京到西安的最短路径；求北京到沈阳的最短路径；求北京到武汉的最短路径。 这里路径指两顶点间的通路，路径的长度指所有经过的边的总长。“最短路径”的问题指当两个顶点间通路多于一条时，如何找出边长总和为最短的那条。Dijkstra提出按路径长度递增的次序求最短路径的方法。 Dijkstra 求最短路径的基本思想 把顶点分成两组，第一组是已确定最短路径的结点的集合，第二组是尚未确定最短路径的结点的集合。按路径长度递增的次序逐个把第二组的顶点放到第一组中。设求从v0到其它各顶点间的最短路径,则在任意时刻，从v0到第一组各顶点间的最短路径都不大于从v0到第二组各顶点间的最短路径。 Dijkstra 求最短路径的步骤 设图以邻接矩阵arcs存储，矩阵中各元素的值为各边的权值。顶点到自身的权值用0表示，顶点间无边时其对应权值用-1表示。从顶点v0到其它各顶点间的最短路径的具体步骤如下： （1）初始化：第一组（集合s）只含顶点v0,第二组（集合v-s）含有图中其余顶点。设一D向量，其下标是各顶点，元素值是顶点v0到各顶点的边的权值。若v0到某顶点无边，D向量中的对应值为-1。 （2）选D中最小的权值，将其顶点（j）加入s集合。 s=s {j}