近年来,随着智能交通系统、通信系统等的不断发展,网络出现了新的特性—动态特性和大规模特性。对于具有新特性的网络中的最短路径问题的研究具有重要的理论意义和应用价值。这两类问题与传统的最短路径问题比起来,更加复杂,计算量也更大。当网络规模很大时,求解更加复杂,计算时间和所需的存储空间也大大的增加。并行计算,为快速地求解动态网络和大规模网络中的最短路径提供了一个有效的途径。 本文首先对时间依赖网络与大规模网络的特性进行了深入研究。接下来,对于时间依赖网络,设计了结点分解型的并行方法来划分网络数据,并根据分而治之的思想,利用SPMD模式设计了分布式环境下求解时间依赖网络最短路径的细粒度并行算法,该算法能够有效求解时间依赖网络中多结点到任意给定目的结点的最优路径;对于大规模网络,利用网络树模型对网络进行划分,采用动态分配策略来对数据进行分配,并采用Master/Slave模式设计了求解大规模网络最优路径的粗粒度并行算法,该算法大大提高了计算效率,并降低了大规模网络优化对内存的需求。 最后,建立了基于PVM的PC集群并行计算平台,并对这两个最短路径并行算法的性能进行了实验测试,给出了算法的运行时间、加速比和效率,并讨论了负载平衡问题和提高并行性能的具体方法。实验结果表明,本文所设计的并行算法在解决动态网络和大规模网络中的最短路径问题上是非常有效的。