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