1、 上海电力学院 本科毕业设计（论文） 题 目： 电子地图与最短路径算法的结合 院 系： 数理学院 专业年级： 信息与计算科学专业 2009 级 学生姓名： xx 远 学号： 20092426 指导教师： 宋政芳 2013 年 6 月 3 日 上海电力学院学士学位论文 - I - 摘 要 最短路径问题 在 图论 研究中是 一个 长盛不衰的 经典 问题 ，旨在寻找图中 指定两结点 间的最短路径 ； 而电子地图 如今蓬勃发展， 依托 计算机成象等技术，直观的为人们服务。 电子地图 需要 借助最短路径算法，得出 指定 起始点至目的地， 并且 同时 满足需求的行进路线。 二者的结合，在促进彼此发展的同时
2、， 更 为人们提供越发显著的帮助。 而探讨二者结合，一方面要学习最短路径问题，了解当前已知的最短路径算法，如 适用于单源非负的 Dijkstra 算法，所有顶点之间的可负的 Floyd 算法 等；另一方面要懂得电子地图是如何将现实中的交通网络数据化，抽象为一般有向图 。 电子地图与最短路径算法结合的前提是电子地图的“绘制”：无论是对哪 种最短路径算法，他们得以实施，实 现的前提都是有向图或无向图的出现。 而 在“绘制”电子地图时，最为关键的就是建立城市交通网络数据模型。 电子地图与最短路径算法结合的核心是 最短路径 算法的实现：如何在已知的交通有向图或无向图上，实现最短路径算法，得到所求路径，并保证准确有效的到达，是电子地图与最短路径二者结合最突出，最核心的问题。 关键词： 电子地图 ； 最短路径算法 ； 数据模型
