1、 课程课程: 算法与数据结构算法与数据结构 最短路径最短路径-拯救拯救 007 课程设计课程设计 系系 电子信息与计算机科学系电子信息与计算机科学系 专业专业 计算机科学与技术计算机科学与技术 班级班级 * 姓名姓名 * 学号学号 * * 任课教师任课教师 学年学期学年学期 学期学期 1 任务分配： 程序员：*。 主要任务：负责算法的设计，并完成源代码的编写。 测试员：*。 主要任务：负责设计测试用程序，并对实验结果进行整理分析，最后完成实验报告的第 三、第四部分内容，即测试结果与分析探讨部分。 文档员：*。 主要任务：负责撰写实验报告的第一、第二部分内容，即实验内容简介与算法描述。同 时完成
2、整个文档的整合，使整篇报告排版、文字风格统一。 一、简介 看过 007 系列的电影的人们一定很熟悉 Jams Bond 这个世界上最著名的特工了。在 电影“Live And Let Die”中 Jams Bond 被一组毒品贩子抓住并关到湖中心的一个小岛上， 而湖中有很多凶猛的鳄鱼。这时 Jams Bond 做出了他跳到了最近的鳄鱼的头上，在鳄 鱼还没有反映过来的时候， 跳到另一支鳄鱼的头上最后终于安全地跳到 了湖岸上。 假 设湖是 100*100 的正方形，设湖的中心在（0，0） ，湖的东北角的坐标是（50，50） 。湖中 心的圆环小岛的圆心在（0，0） ，直径是 15，一些凶残的鳄鱼分布在
3、湖中不同的位置。现已 知的湖中的鳄鱼的位置和 Jams Bond 可以跳的最大距离，请你告诉 Jams Bondyitiao 最短 的到达湖边的路径。他逃出去的路径长度等于他跳的次数。 其中最短路径说的是在一个无权图中， 若从一个顶点到另一个顶点存在着一条路径， 则 称该条路径长度为该路径上所有经过的边的数目，它也等于该路径上的顶点数减 1。由于从 一个顶点到另一个顶点可能存在着多条路径， 在每条路径上所经过的边数可能不同， 把路径 长度最短（经过的边数最少）的那条路径叫做最短路径，其路径长度叫做最短距离。若图是 帯权图， 则把从一个顶点 vi 到 vj 的一条路径上所有经过边的权值之和定义为
4、该路径的带 权路径长度。 把带权路径长度最短的那条路径称为该有权图的最短路径， 其路径长度称为最 短距离。如何求解从一个顶点到其余每个顶点的最短路径呢？狄克斯特拉于 1959 年提出了 解决此问题的一种按路径长度的递增次序产生最短路径的算法。 其基本思想是， 从图中给定 源点到其他各个顶点之间客观上应个存在一条最短路径， 在这组最短路径中， 按其长度的递 增次序求出到不同顶点的最短路径和路径长度。 另外上文提到的图是一种较线性结构和树形结构更为复杂的非线性数据结构， 这种复杂 性主要来自数据元素之间的复杂关系。 在图结构中， 任何两个数据元素之间都可能存在关系， 一般用顶点表示数据元素， 而用
5、顶点之间的连线表示数据元素之间的关系。 图的二元组定义 为：G=(V,E)。其中 V 是非空的顶点集合，E 是 V 上的二元关系集合。 二、算法说明 2.1 输入、输出要求 输入要求： 程序从 “input.txt” 文件中读取输入信息， 这个文件包含了多组输入数据。 每组输入数据的起始行中包含了两个整数n 和d， n 是鳄鱼的数量而且n0。起始行下面的每一行是鳄鱼的坐标（x,y） ， 其中 x,y 都是整数， 而且没有任何两只鳄鱼出现在同一位置。Input.txt 文件以 一个负数结尾。 输出要求： 程序结果输出到 output.txt 文件中。对于每组输入数据，如果 007 可以 逃 脱，
6、则输出到 output.txt 文件的内容格式如下：第一行是 007 必须跳的最小步 数，然 后按照跳出顺序记录跳出路径上的鳄鱼坐标（x,y） ，每行一个坐标。如果 007 不可能跳出 2 去，则将-1 写入文件。如果这里有很多个最短路径，只需输 入其中的任意一种。 2.2 所用算法和重要的数据结构 首先可定义为如下结构，记录 007 跳过的路径。 typedef unsigned int Vertez; typedef double Distance; typedef struct GraphNodeRecord int X; /*x 轴坐标*/ int Y; /*y 轴坐标*/ unsigned int Step; /*记录到本节点一共跳了多少步*/ Vertex Path; /*指向本节点的父节点，即跳到本节点之间 007 所在节点*/ GraphNode; typede
