DOC《实验报告》

实验报告最短路径专业班级:02计算机2班姓名:冯绍欣学号:2002374203 华南农业大学信息学院 设计性、综合性实验 起止日期:2004-2005学年度第一学期 系别 计算机 班级 02计1 学号

2002374125 姓名 许迪飞 实验题目讨论并实现一种GIS 环境下的最短路径规划算法,根据用户给出的起始结点与目标结点以及必经结点序列和避开结点序列在建立的搜索图基础上分段查找最短路径,最后生成满足用户约束条件的最短路径.

最短路径即可理解成经过顶点数最少的路径,亦可理解成路径长度最小的路径. 设计性 综合性 自我评价这次的设计作业真的很难!尤其是那输出路径的算法.我请教了好几位同学,才编出适合自己程序的算法.难关终被攻破,我对这次的作业还比较满意,毕竟是花了很多功夫.通过这次设计,我想我对图的概念,性质有了更新的了解 教师评语能够实现实验要求的(全部)(部分)功能, 算法(有新意)(一般),程序(全部)(部分)运行通过, 算法注释说明(完善)(仅有功能说明)(没有),(有)(无)接口参数说明,按期上交(所有)(部分)打印文档资料及源程序,综合设计说明报告结构(合理)(不合理),用户使用说明(完整)(不全),现场演示操作(有)(无)准备,问题解答(流畅)(不流畅),(能)(不能)独立完成实验,(能够)(不能)体现团队合作精神. 成绩 最短路径操作说明: 实现GIS无向有权图的最短路径算法,根据用户给定的起始结点与目标结点以及必经结点和避开结点在建立的搜索图基础上查找最短路径,最后生成满足用户约束条件的最短路径. 运行后,显示: SHORTEST PATH GIS:V0,V2,10>,;

, ,;

, ,;

, ,;

, The threshold: 相关的路径和权值,并提示输入起点.然后有输出: The end point: 提示,要求输入终点.继续运行: input the unavoidable nodes (end with -1 ): 提示输入必须经过的点,直接输入-1,默认路径不受限制. 继续: input the avoidable nodes (end with -1 ): 提示输入必须避开的点,直接输入-1,默认路径不受限制. 最后输出结果 the shortest path from V? to V? is :

2 注意事项:

1 此算法再实现"通过经过必经点"的时候,由于采用了"以必经点为折点的分段求最短路径,再相加最短路径,得最短"的思想,同是输入相同的两个点,由于顺序的不同,会有不同的结果.因此用在输入必经点的时候必须注意顺序的问题.换句话说,用户必须确定先要经过那个点,再到令一个点.否则,系统会输出不是你想要的结果.

2 由于采用路径初此化,若用户想更改路线必须在源程序里面修改,这是为了测试方便. 给用户带来不便,我们十分抱歉.

3 测试数据: 运行: SHORTEST PATH GIS:V0,V2,10>,;

, ,;

, ,;

, ,;

, The threshold:5 The end point:1 input the unavoidable nodes (end with -1 ):0

4 -1 input the avoidable nodes (end with -1 ):-1 the shortest path from V5 to V1 is : V5-> V3-> V4-> V0-> V4-> V0-> V2-> V1 Continue (y/n)? The threshold:0 The end point:5 input the unavoidable nodes (end with -1 ):2 -1 input the avoidable nodes (end with -1 ):4 -1 the shortest path from V0 to V5 is : V0-> V2-> V3-> V5 Continue (y/n)? The threshold:5 The end point:3 input the unavoidable nodes (end with -1 ):2

0 1 -1 input the avoidable nodes (end with -1 ):4 -1 the shortest path from V5 to V3 is : V5-> V3-> V2-> V0-> V2-> V1-> V2-> V3 Continue (y/n)? The threshold:6 The end point:1 input the unavoidable nodes (end with -1 ):-1 input the avoidable nodes (end with -1 ):-1 No the path! Continue (y/n)?