最优路径问题是计算机科学、运筹学、工程设计等领域众多问题的基础。它的应用十分广泛，涉及网络路由、电路设计、交通运输、机器人运动规划、事务调度中关键路径的计算以及VLSI设计等。同时，它也为很多最优化问题提供了解决框架，如背包问题、分子生物学中的序列比对、内接多边形的构造和长度受限的霍夫曼编码等都可以转化成最优路径问题进行求解。　　 求解网络中单源最优路径的方法可以分为两类。一种是标号设定算法( labelsetting，LS)，另一种是标号改变算法(label correcting，LC)。由于网络路径算法的应用越来越强调动态性和及时性，使得高效求解最优路径问题变得越来越重要。在本文，我们利用一种高效的网络划分方法，实现了基于网络划分的LS/LC并行算法。实验结果表明，这种基于网络划分的求解最优路径并行算法有很好的加速比和扩展比。　　 在许多更为复杂的应用中，不仅要求计算出最优路径，而且要求给出前K优路径，即要求不仅得到最优路径，还要得到次优、再次优等路径。K优路径是长期研究的泛化最优路径问题，节点s到节点t的K优路径问题可以分为两大类：一类是求解K优非简单路径，即得到的路径可以包含环路；另一类是求解K优简单路径，即路径是简单通路，不包含环路。经过大量学者的研究，求解K优非简单路径相对容易。Fox于1975年提出了复杂度为O(m+kn logn)的求解K优非简单路径的算法，Eppstein于1998年给出了一种优化的求解K优非简单路径算法，时间复杂度达到了O(m+nlogn+k)，基本上达到了理论下限。E.Ruppert在2000年对EEppstein的算法进行并行化，得到了时间复杂度为O(logn+logk)的并行算法。求解K优简单路径问题最先由Pavley和Hofman在1957年开始进行研究，但几乎所有试图解决该问题的算法时间复杂度都为指数时间。Yen在1971年利用现代的数据结构得到一较好的算法，使时间复杂度达到O(kn(n+nlogn))。John Hershberger于2007年给出了一个新的求K优路径的算法，该算法基于有效的替代路径算法，相对于以前的替代路径算法，其加速比可达到O(n)。在本文中，作者基于John Hershberger给出的K优路径算法，尝试给出其并行的方法，并在SMP的高性能计算机上进行了实验。