《电子地图与最短路径算法结合精简版资料.docx》由会员分享，可在线阅读，更多相关《电子地图与最短路径算法结合精简版资料.docx（5页珍藏版）》请在三一文库上搜索。
1、电子地图与最短路径算法的结合专业：信息与计算科学学生姓名：xx远指导老师：宋政芳摘要最短路径问题在图论研究中是一个长盛不衰的经典问题，旨在寻找图中指定两结点间的最短路径。而电子地图如今蓬勃发展， 依托计算机成象等技术， 直观呈现面画来为人们 服务。电子地图需要借助最短路径算法，得出指定起始点至目的地的行进路线，而最短路径算法通过电子地图建立使用渠道，二者的结合相互融合间又相互促进。其结合前提是电子地图的绘制，核心是最短路径算法的实现。关键词电子地图；最短路径算法；数据模型The Combination of Electronic Map and the Shortest PathAlgorit
2、hmAbstract: 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 shor
3、test 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 ；
4、Shortest Path Algorithm ； Data Model前言科技让世界更紧密，人们的脚步不断在一个个陌生的城市留下足迹。在陌生的地方，如何到达目的地，如何正确到达目的地，如何快速正确到达目的地，是出行者不得不考虑的问题。随着外出频率和距离的增加，电子地图的使用次数与范围不断增加。电子地图的应用方面，最主要的有两个领域：一为模拟地貌地形，一为依托最短路径算法实现最短路程的选择。现实民用方面，第二部分无疑更受关注和使用。电子地图与最短路径算法的结合已称为必须，在生活节奏快速的今天更是一种必然。这种结合的作用是显然的，而这种结合的难度也是易见的，前期工作量极大。电子地图与最短路径算法
5、结合的前提是电子地图的“绘制”，只有将现实道路网络抽象为一般有向图或无向图，才能以此基础去实现算法；电子地图与最短路径算法结合的核心是最短路径算法的实现，实现最短路径算法之后，才能根据实际需求，寻求满意服务。一、基本概念在本文里，主要涉及图论，最短路径问题和电子地图三大部分的知识点。首先介绍图论时，给出了图，度数等基本概念，这些都是最短路径算法实现的基础。同时，对邻接矩阵，邻接表进行定义，依托这两个存储图的方法，实现不同的最短路径算法1L其次介绍最短路径问题时，给出了该问题的基本定义，以及在不同情况，不同要求下的 定义，由浅入深，对该类问题的认知不断增加。最后介绍电子地图时，给出其基本性质，一
6、般特点，以及开发所依托的地理信息系统的 信息，让读者在进入课题正式研究介绍前，对课题有一定的了解。二、最短路径算法在如今发展中，尚未出现一个明确，可靠的评价标准去评判哪个或哪几个最短路径算法 是最优的。随着研究的深入，最短路径算法的种类也不断增加，现在比较常用的最短路径算法有：Dijkstra算法、Bellman - Ford算法、SPFA算法、Floyd算法等，比较有特征的算法有A*（A-Star怦法等2乂。本文着重介绍Floyd算法，该算法适用于求多源、无负 权边的最短路径。1. Floyd算法的思想：设D（i, j,k ）为从i至1J j中只以顶点集合 V中的某个顶点k为中间节点的最短路
7、径的长 度。若最短路径经过点 k ,则D（i, j,k）=D（i,k, k 1）+D（k, j,k 1）;若最短路径不经 过点 k ,则 D（i, j,k ）=D（i, j,k1 卜因此D i,j,k =min D i,k,k-1 D k,j,k-1 ,D i,j,k-12.1由上述公式可知：在原有路径的基础上加入其它顶点为中间节点后，若距离缩小，便以新路径替代原有路径。不断更新后，即可得到最短路径。在实际算法中，为节约空间，可以 直接在原来空间上进行迭代，从而空间可降至二维。2. Floyd算法的实现对拥有n个顶点的有向图而言，设置一个niendendendfor k=1:nfor i=1:nfor j=1:nif D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k);endendend end