随着当前城市规模的不断扩大,交通网络越来越复杂,出现了动态性和大规模性的新特征。对新特性网络的最短路径问题研究变得更有现实价值。与传统小规模网络相比较,大规模网络中会出现成百上千甚至上万个顶点,使得最短路径求解变得更加复杂化,计算量也更加庞大。同时计算消耗的时间和所需的存储空间也将增加。随着计算机网络技术的不断发展,使基于网络的分布式并行计算技术得到了较快发展,出现了大量并行算法。从而为快速求解大规模网络的最短路径问题提供了一种高效的途径。本文首先对并行计算基础知识进行了简单介绍,包括并行计算机模型,并行算法设计方法,提高并行算法的几个关键因素及目前运用较多的并行环境。结合本文研究内容,文章中对规模较大的城市交通网络进行分析,提取特征,然后给出了大规模城市路网的宏观和微观模型,建立了交通路网的图结构。接着对经典串行Dijkstra算法进行并行化设计,采用Master/Slave模式来具体实现求解大规模网络最短路径的细粒度并行算法,并在MPI并行环境下对算法进行了实验验证,从理论上分析,并行化后使算法复杂度由O(N2)减到O(N2/p+N*(p-1)),提高了算法的效率。针对具体的大规模交通网络来说,运用并行方法求解最短路径的过程中,对交通网络的分割起着很关键的作用,文章中给出了几个常用的分割方法,并对他们各自的优缺点进行了说明,本文采用Metis图划分方法对网络进行分割,通过修改Metis库中源文件,提取出计算最短路径所需的相关信息。同时给出了分层并行求解最短路径思想,并在多机下环境下实现了最短路径查询。具体针对西安市电子地图,本文分成两层来对路网进行化简,采用分而治之的思想策略，采用SPMD模式在分布式环境下对最短路径进行求解,求解过程中采用了上述的并行搜索算法。运用该方法大大提高了计算效率,节省了时间开销,同时降低了对计算机的内存存储需求。负载平衡问题几乎是所有并行计算都要考虑的问题,本文同时提出了一种基于益处评价函数的负载平衡策略,运用并行快速排序算法对其进行了验证,取得了较好的实验效果。该方法对同类问题具有很好的借鉴价值。最后文章简单介绍了并行计算环境,基于消息传递模式的MPI(Message Passing Interface)运行平台,结合本文,通过搭建PC集群并行试验平台,用VC++6.0为编译环境,对三部分内容进行了实验测试,(1)对并行Dijkstra算法的测试；(2)结合西安市电子地图,运用Mapinfo软件将地图信息导出,在PC机群的并行环境下对其进行实现。实验结果表明,该方法在运行时间和内存空间分配都具有明显的优势,具有良好的实用性。(3)对负载平衡策略进行测试,获得了较高的执行效率。