最短路径问题的研究在汽车实时导航、应急救援等领域有广泛的应用。经典的Dijkstra算法是应用最短路径解决实际问题的理论基础。但是算法在具体的城市道路网络中执行的效率比较低，无法满足实时高效的应用需求，因此国内外很多学者对算法的优化与完善做出了深入的研究。 传统的优化算法在设计的过程中只考虑了抽象网络的拓扑特性，忽略了具体的道路网络存在着空间特性。随着WebGIS、移动GIS与GPS定位技术的结合，动态路径规划将是今后的发展方向。动态路径规划需要通过Internet获取实时的路况信息、更新路段权值，再调用最短路径算法求解。传统的优化算法却没有考虑到传输、更新的数据量对算法整体性能的影响。使用控制路网规模的方法能够克服传统方法的不足，同时又可以与传统算法组合使用，进一步提高最短路径算法的性能。 本文用新的技术路线和方法对传统的最短路径问题进行了系统研究。通过对上海地区随机抽取的最短路径统计特征的分析和样本路径空间分布特征的观察，构建了适用于一般道路网络的椭圆模型和适合于上海道路特征的椭圆模型参数。该模型将两点之间的最短路径搜索范围限定在椭圆范围内，这种算法大幅度减少了冗余节点，减轻了网络传输实时路况数据的负担，提高了算法的性能和效率。使用椭圆模型改进后的算法在理论上搜索扫描过的空间范围约为经典算法的1／5。 同时，本文针对上海市道路网络，在大量随机抽样的基础上，研究了欧氏距离、马氏距离和最短路径之间的关系。研究发现最短路径的长度分别与路径的起终点连线的欧氏距离和马氏距离之间存在着显著的线性关系。通过回归分析，分别得到最短路径长度与两者的直线回归方程。用欧氏距离拟合的最短路径长度与样本最短路径长度的相对误差分布集中在-7.5％至7.5％之间，通过F检验，在α=0.01的置信水平下显著。而使用马氏距离拟合精度偏低。因此，在只需要求解两点之间最短路径长度的情况下，可以将两点连线的欧氏距离代入方程直接计算。 对于上海的道路网，通过典型抽样选取有代表性的节点，将本文提出的椭圆模型与经典的Dijkstra算法、其他学者提出的限制搜索范围模型计算最短路径算法，进行了准确度、搜索规模和搜索性能3个方面的比较，结果表明：本文研究的椭圆模型准确率达到99.8％，搜索规模和算法执行时间分别为经典算法的50％和16.6％。相比于另外两种椭圆模型，本文的椭圆模型比陆锋(1999)的算法具有更高的效率，比Hui Wang(2003)的算法具有更高的准确性，综合性能比较结果，本文提出的椭圆模型更好。