电子地图与最短路径算法结合精简版

电子地图与最短路径算法的结合

专业:信息与计算科学学生姓名:xx远指导老师:宋政芳

[摘要]最短路径问题在图论研究中是一个长盛不衰的经典问题,旨在寻找图中指定两结点间的最短路径。而电子地图如今蓬勃发展,依托计算机成象等技术,直观呈现面画来为人们服务。电子地图需要借助最短路径算法,得出指定起始点至目的地的行进路线,而最短路径算法通过电子地图建立使用渠道,二者的结合相互融合间又相互促进。其结合前提是电子地图的绘制,核心是最短路径算法的实现。

[关键词]电子地图;最短路径算法;数据模型

The Combination of Electronic Map and the Shortest Path

Algorithm

Abstract: The shortest path problem in graph theory is an enduring problem, aims to find the shortest path between two specify nodes of the graph. With the development of electronic maps which depends on computer imaging technology, it service for people intuitively. Electronic map need use a shortest path algorithm, and gets the road from the starting point to destination. This combination promotes the development of each other. Meanwhile the combination is the premise of electronic map in the "drawing" and the core of the realization of the shortest path algorithm.

Key Word: Electronic Map;Shortest Path Algorithm;Data Model

前言

科技让世界更紧密,人们的脚步不断在一个个陌生的城市留下足迹。在陌生的地方,如何到达目的地,如何正确到达目的地,如何快速正确到达目的地,是出行者不得不考虑的问题。随着外出频率和距离的增加,电子地图的使用次数与范围不断增加。

电子地图的应用方面,最主要的有两个领域:一为模拟地貌地形,一为依托最短路径算法实现最短路程的选择。现实民用方面,第二部分无疑更受关注和使用。电子地图与最短路径算法的结合已称为必须,在生活节奏快速的今天更是一种必然。这种结合的作用是显然的,而这种结合的难度也是易见的,前期工作量极大。

电子地图与最短路径算法结合的前提是电子地图的“绘制”,只有将现实道路网络抽象为一般有向图或无向图,才能以此基础去实现算法;电子地图与最短路径算法结合的核心是最短路径算法的实现,实现最短路径算法之后,才能根据实际需求,寻求满意服务。

一、基本概念

在本文里,主要涉及图论,最短路径问题和电子地图三大部分的知识点。

首先介绍图论时,给出了图,度数等基本概念,这些都是最短路径算法实现的基础。同时,对邻接矩阵,邻接表进行定义,依托这两个存储图的方法,实现不同的最短路径算法[]1。

其次介绍最短路径问题时,给出了该问题的基本定义,以及在不同情况,不同要求下的定义,由浅入深,对该类问题的认知不断增加。

最后介绍电子地图时,给出其基本性质,一般特点,以及开发所依托的地理信息系统的信息,让读者在进入课题正式研究介绍前,对课题有一定的了解。

相关推荐
相关主题
热门推荐