1、 本科毕业设计（论文）本科毕业设计（论文） 题 目：电子地图与最短路径算法的结合 院 系： 数理学院 专业年级： 信息与计算科学专业 2009 级 学生姓名： xx 学号： 指导教师： xx 2013 年 6 月 3 日 上海电力学院学士学位论文 - I - 摘 要 最短路径问题在图论研究中是一个长盛不衰的经典问题， 旨在寻找图中指定 两结点间的最短路径；而电子地图如今蓬勃发展，依托计算机成象等技术，直观 的为人们服务。电子地图需要借助最短路径算法，得出指定起始点至目的地，并 且同时满足需求的行进路线。 二者的结合，在促进彼此发展的同时，更为人们提供越发显著的帮助。而探 讨二者结合，一方面要学
2、习最短路径问题，了解当前已知的最短路径算法，如适 用于单源非负的D ijkstra算法，所有顶点之间的可负的F loyd算法等；另一方面 要懂得电子地图是如何将现实中的交通网络数据化，抽象为一般有向图。 电子地图与最短路径算法结合的前提是电子地图的“绘制” ：无论是对哪种 最短路径算法， 他们得以实施， 实现的前提都是有向图或无向图的出现。 而在 “绘 制”电子地图时，最为关键的就是建立城市交通网络数据模型。 电子地图与最短路径算法结合的核心是最短路径算法的实现： 如何在已知的 交通有向图或无向图上，实现最短路径算法，得到所求路径，并保证准确有效的 到达，是电子地图与最短路径二者结合最突出，最
3、核心的问题。 关键词：关键词：电子地图电子地图；最短路径算法最短路径算法；数据模型数据模型 电子地图与最短路径算法的结合 - II - II 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 diagrams specify the shortest path between two nodes. With the development
4、of electronic maps which depends on computer imaging technology, it service intuitively for people. Electronic map need use a shortest path algorithm, and gets the road from the starting point to destination, and meets the demand of route at the same time. The combination of both, in promoting the d
5、evelopment of each other at the same time, more people gain increasingly significant help. And explore this combination, on the one hand to study the shortest path problem, understand the currently known shortest path algorithm, such as Dijkstra algorithm dispose for single-source non-negative, Floy
6、d algorithm manage between all vertices of the algorithm can be negative, on the other hand to understand digital electronic map is how to real traffic network, the abstract is typically directed graph. Electronic map combined with the shortest path algorithm is the premise of electronic map in the “drawing“: for all of shortest path algorithm, they can implement, implementation is the premise of directed graph or undirected graph. In the “drawing“ electronic map, the key
