最短路径问题在实际生活中的应用
时间:2017-03-27 20:53 来源:毕业论文 作者:毕业论文 点击:次
| 摘要：最短路径问题是图论的一个经典问题。本论文主要对解决最短路径问题的Dijkstra算法和Floyd算法进行了分析，然后运用这两个算法解决了最短路径问题在城市公交系统、旅游路线选择和矿区的选址方面的应用，为企业和个人提供了方便，因此不仅具有重要的理论意义，而且具有重要的实用价值。6885 关键词：最短路径；Dijkstra算法；Floyd算法 The Application of Shortest Path Matter in Actual Life Abstract：The shortest path matter is a classical problem of graph theory. In this article , I mainly analyse two algorithms solving the shortest path problem-Dijkstra algorithm and Floyd algorithm, and then use them to explain the application of the shortest path matter in some sectors such as city public transportation system,the choosing of travel route and the address choosing of mining areas, which provides convenience for companies and personals. so it’s not just important in theory sense, but also very valuable in solving practical problems. Key words：Shortest Path；Dijkstra Algorithm；Floyd Algorithm目 录 摘 要 1 引言 1 1.绪论 2 1.1最短路径问题的研究现状 2 1.2最短路径问题的研究的意义和内容 2 1.3预备知识 3 2.最短路径问题的算法 4 2.1 Dijkstra算法 5 2.2 Floyd算法 6 2.3 算法 8 3.最短路径问题的应用 8 3.1 Dijkstra算法的应用 9 3.2 Floyd算法的应用 12 参考文献 14 致谢 15 最短路径问题在实际生活中的应用 引言 在科学不断进步，生产的社会化和专业化程度不断提高的今天，一切物质产品的生产消费都离不开最短路径问题的选择，快捷的的城市公交路线，最佳旅游路线、科学合理的物流运输路线都是最短路径的问题。最短路径在当今社会中显得愈来愈重要。它不仅节省了人们大量的时间，降低了配送成本，方便了人们的生产和生活还提高了服务质量、增加了公司的经济效益，从而提高了产品的竞争力，为现代化的发展打下良好的基础。本文通过正确运用Dijkstra算法和Floyd算法来解决生活和生产中最短路径的相关问题。 1. 绪论 1.1 最短路径问题的研究现状 1.2 最短路径问题的研究的意义和内容 随着社会生活的不断进步，如何提高生活的效率成为了关键，因此最短路径算法在人们的日常生活中显得愈来愈重要。人们乘坐公交或者开车去上班的时候，选择一条怎样的公路才能使自己乘车到公司的时间最短或者到公司的费用最低，这是最短路径问题，在旅游游览中，如何选择一条者最省时，最有效旅游方案这也是最短路径问题，还有在选址过程中，如何选择一个合适的地址才能达到资源的最优利用和费用的最少，这还是最短路径问题。这些问题与人们的生活息息相关。此外随着工业技术的发展，汽车被应用到各个行业领域，但是也给大城市的交通事业带来了很大的压力，当今社会面临着交通拥堵，交通环境恶化等问题。因此找出最短路径对于缓解交通有着十分重要的现实意义，本文针对城市交通、旅游方案、选址问题等有关问题进行了分析，从而找出最短路径，节约时间，方便人们的生活和生产，提高人们生活的质量和效率。所以最短路径问题在我们的生活中有着不可忽视的作用[4]。 本文的主要内容为：第一章，给出了最短路径问题的研究现状、研究意义和基本定义；第二章，介绍了解决最短路径问题的几种常见算法，如Dijkstra算法、Floyd算法；第三章，主要给出了最短路径算法的在实际生活中的应用，如城市公交系统等问题。 (责任编辑：qin) |