单源结点最短路径问题设计书

1 单源结点最短路径问题设计书 1 设计内容 单元结点最短路径问题。 问题描述：求从有向图中的某一结点出发到其余各结点的最短路径。 基本要求： （ 1）有向图采用邻接矩阵表示。 （ 2）单元结点最短路径问题采用狄克斯特拉算法。 （ 3）输出有向图中从源结点到其余各结点的最短路径和最短路径值。 测试数据：如下图有向带权图所示 2 算法思想描述 狄克斯特拉算法思想：设置两个顶点的集合 S 和 T，集合 S 中存放已找到最短路径的顶点，集合 T 中存放当前还未找到路径的顶点。初始状态时，集合 S 中包含源点，设为 后从集合 T 中选择 径长度最短的顶点 u 加入到集合 S 中，集合 S 中每加入一个新的顶点 u，都要修改源点 集合 T 中剩余顶点的当前最短路径的当前最短路径长度值，集合 T 中各顶点的新的当前最短路径长度值为原来的当前最短路径长度值与从源点过顶点 u 到 达该顶点的路径长度中的较小者。此过程不断重复，直到集合 T 中的顶点全部加入到集合 S 中为止。 3 算法及程序实现 # # /定义顺序表的数据类型为 0 /定义顺序表数组的最大个数 #0 /定义顶点的最大个数 #0000 /定义权值的具体最大 值 # /包含 文件 # /包含 文件 2 # /包含 数的文件 g; a=A,B,C,D,E,F; = 0,1,10,0,2,12,1,3,16,1,4,25,2,0,4,2,1,3,2,3,12, 2,5,8,3,4,7,5,3,2,5,4,10; i,n=6,e=11; ,; g,a,n,e); g,0, nt 从顶点 %c 到其余各顶点的最短路径值分别为 :n,); i=1;ij=0; -ij= /示无穷大 5 G-; /边的条 数置为 0 /顺序表初始化 G, /在图 G 中插入顶点 - /顺序表尾插入 G,v1,v2, /在图 G 中插入边 ,边 的权为 if( 参数 界出错 !n); G-G-; G,v1, if( 参数 界出错 !n); -= 该边不存在 !n); G-G- 6 ,v) /在图 G 中寻找序号为 V 的顶点的第一个邻接顶点 /如果这样的邻接顶点存在，则返回该邻接顶点的序号；否则返回 if( 参数 界出错 !n); 1; ;v 参数 界出错 !n); 1; ; /定义初始数据元数个数 ) /返回顺序表 L 的当前数据元数个数 L,i,x) /在顺序表 L 的第 i(0= 9 顺序表已满无法插入 !n); ; if( 参数 i 不合法 !n); ; /从后向前依次后移数据，为插入做准备 j=L-ji;-j=L- L-i=x; /插入 x L-; /元素个数加 1 ; L,i,x) /删除顺序表 L 中位置 i(0- 参数 i 合法 !n); ; *x=L-i; /保存删除的元素到 x 中 /从前向后依次前移 j=i+1;j+)L-L-j; L- /数据元素个数减 1 ; 10 ,i,x) /取顺序表 L 中第 i 个数据元素存入 x 中，成功返回 1，失败返回 0 if( 参数 i 不合法 !n); ; *x=i; ; 11 心 得 体 会 课程设计是培养学生综合运用所学知 识 、 发现 、 分析和解决实际问题 ,是对学生实际工作能力的具体训练和考察过程 今软件技术 应用在生活中可以说得是无处不在。因此 对于 二十一世纪的大学 生 来说掌握 软件 开发技术是十分 必要 的。 在设计的过程中，我遇到了 很多 的问题，有时 对于程序运行错误 甚至束手无策。发现 要 设计出规范的算法程序是 一 个 不断发现缺陷 、改进缺陷的艰难过程 。经过老师的指导、同学们的帮助，再加上自己坚持 与探索 ， 终于 设计出一个比较合理的算法程序。虽然 程序还 存在诸多 的不足 ， 但是我 相信随着学习的深入，实践的改进，我的程序设计能力会得 到很大 提高 的。 通过这次课程设计，我学到了很多， 体会 了很多，不仅将在书本中学到的知识运用到解决实际问题上，而且 体会到了程序设计过程的艰难。这是我这次课程设计的经验和心得，并希望老师能够批评指出存在的错误之处，期待有更多的机会让我实践理论知识。 总的来说，这次课程设计确实学到很多