陈丽萍图论作业陈丽萍图论作业.doc

图论及其应用 论文题目：重庆歌乐山任意景点间最短路径问题 2013-2014学年第 一 学期 指导教师 蒲兴成 科 目 图论及其应用 姓 名 陈丽萍 学 号 S130131008 专 业 电子与通信工程 2013年 12 月 9 日 重庆歌乐山任意景点间最短路径问题 摘要：从300多年前的诞生以来，图论以它描述和解决问题直观有效等特点，成为了人们研究的重要方法，在实际中也得到广泛应用。本文简单介绍了图论的发展与特点，阐述了任意两点间最短路径问题及其算法。并采用Floyd-Warshall 算法来解决重庆歌乐山任意景点间最短路径问题，介绍算法的思想、过程，最后用C++实现。通过运行比较，结果与理论一致，任意两点间最短路径问题。 【关键字】 任意的 最短路径 Floyd-Warshall算法 导游图 C++ The problem of Qixing geleshan shortest path between any two points on Floyd-Warshall Abstract：Since the birth of graph theory 300 years ago , it has become an important research method with its intuitive and effective characteristics . It has also be widely used in practical. This paper briefly describes the development and characteristics of graph theory，and explain the problem of shortest path between any two points and its algorithm also. Moreover，the paper use Floyd-Warshall algorithm to solve The problem of Qixing geleshan shortest path between any two points .At the same time, it the idea process of the algorithm and finally implement it by C++ . By comparing the theoretical and running results，we can achieve the target. 【Key Words】any two points shortest path Floyd-Warshall algorithm tour map C++ 一．绪论 1736年瑞士著名的天才数学家欧拉提出了著名的哥尼斯堡七桥问题，这是历史上第一篇图论的论文，它的发表标志着图论作为一门科学诞生了。在19世纪，许多关于图论的重要结论就已经得出，但是图论引起广大学者的注意并得以广泛接受和传播是在20世纪20年代以后。 图论的产生和发展经历了二百多年的历史，大体上可分为三个阶段： 第一阶段是从1736年到19世纪中叶。当时的图论问题是盛行的迷宫问题和游戏问题。最有代表性的工作是著名数学家L.Euler于1736年解决的哥尼斯堡七桥问题(Konigsberg Seven Bridges Problem)。 第二阶段是从19世纪中叶到1936年。图论主要研究一些游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题。一些图论中的著名问题如四色问题(1852年)和Hamilton环游世界问题(1856年)也大量出现。同时出现了以图为工具去解决其它领域中一些问题的成果。1847年德国的克希霍夫(G.R.Kirchoff)将树的概念和理论应用于工程技术的电网络方程组的研究。1857年英国的凯莱(A.Cayley)也独立地提出了树的概念，并应用于有机化合物的分子结构的研究中。1936年匈牙利的数学家哥尼格(D.Konig)写出了第一本图论专著《有限图与无限图的理论》(Theory of directed and Undirected Graphs)。标志着图论作为一门独立学科。 第三阶段是1936年以后。由于生产管理、军事、交通运输、计算机和通讯网络等方面的大量问题的出现，大大促进了图论的发展。特别是电子计算机的大量应用，使大规模问题的求解成为可能。实际问题如电网络