嵌入式GPS导航引擎融合了嵌入式平台技术并以此为基础,以及全球定位系统与地理信息系统这三种技术,可以和手持设备相结合,实现移动用户的路径导航、目标定位、位置查询和空间数据分析应用等功能。目前,市面上的各种GPS导航产品通常都是采用集成二次开发,即利用国外专业的GIS工具软件,如ArcGIS、MapInfo等,实现GIS的基本功能,以通用软件开发工具为开发平台,进行二者的集成开发。这种依赖国外商业的GIS工具软件的开发模式,虽然可以使得软件开发的周期大大缩短,但却使得厂商难以减少开发成本,降低产品价格。本论文正是针对上述问题,以导航地图中拓扑关系构建以及最短路径规划为主要研究对象,在深入分析拓扑关系构建和最短路径算法的基础上,对拓扑数据组织结构和最短路径算法作了一定的改进。改进的主要内容为:1.详细研究了导航地图中拓扑关系的构建,全面分析了拓扑元素以及它们之间可能存在的关系,以及如何处理拓扑元素间各种特殊的关系。其次,参考波利维尔特拓扑构建方案,并结合实际城市道路网的特点,改进了拓扑元素的数据组织结构。最后对拓扑关系构建的整个流程作了全面的分析,重点介绍了点线拓扑以及多边形拓扑关系的建立。2.全面分析了传统最短路径算法,如:分别采用邻接表和邻接矩阵存储的Dijkstra算法的优缺点。然后对传统的基于邻接表的Dijkstra算法进行改造,并结合城市道路网实际情况,添加了方向优先搜索功能。使得最短路径算法的效率相比传统Dijkstra算法有了一定的提升,符合导航条件下路径规划的要求。