近年来,中国的快速发展虽然带来了巨大的经济利益,但是随之而来的是巨大的交通压力。车联网系统是提升交通效率、缓解交通拥堵的非常有效的系统,在车联网系统中,导航系统是最为重要的子系统,而最短路径算法部分又是导航系统中最不可或缺的组成部分。早在50多年前,最短路径问题已经被提出了,迄今为止,很多专家学者已经研究分析了不同条件、不同网络模型的最短路径问题,其中当前应用最多的包括Dijkstra、Eiger、Kaufman和Miller-Hooks等人提出的四种不同的理论模型,其中Dijkstra算法是最为经典和成熟的算法。传统最短路径算法在设计过程当中仅考虑到网络拓扑特征,未能兼顾到网络空间分布特征,导致最短路径搜索过程不具备方向性,所以会存在多个与最终查找到的最短路径不相关节点同样参与到计算当中,降低了算法效率,特别是在规模较大的稀疏城市道路网络当中,所应用到的各种算法无法有效满足城市路网实时性需求。首先,本论文建立了城市道路的拓扑模型,提出对城市道路和车辆的经纬度计算方法,并且提炼总结出实际道路的拓扑特点。具体包括:给出预处理经纬度数据的方法,一方面根据城市道路中的经纬度比较精准地计算两个节点之间的路段长度,另一方面把节点的经纬度数据转变为直角坐标表示,并在此基础上归纳总结出城市道路在路段长度与节点取值等方面的固有特点。然后,本论文分别从两个角度对经典Dijkstra算法进行优化。在存储方式上,阐述基于邻接表的Dijkstra算法的实现方式,结果表明邻接表比邻接矩阵大大减少了空间的占用量。在搜索区域限制上,提出椭圆搜索限制和矩形搜索限制的Dijkstra算法的搜索面积大小和确定边界的方式,分别理论推导与分析它们的可靠性和有效性。最后,对优化前后的Dijkstra算法的有效性能分别进行数据统计和仿真验证,结果表明改进的Dijkstra算法不管是在运行速度还是占有空间上都有了很大的提高。最后,本论文按照车联网系统的基本结构,对车载终端和云端的需求和设计方法进行探究,然后给出了车载终端中软件的设计方式。