最短路径--拯救007课程设计.doc

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