NP问题是计算科学中的经典问题,而所有的NP问题都能在多项式时间内归结为NP完全问题,NP完全问题具有相当的复杂性,为NP完全问题寻找一个多项式时间的解法成为了许多科学家的追求,多级图的简单路径问题(MSP)是新近提出的一个NP完全问题,目前已经发现了一个多项式时间的算法ZH算法,但是ZH算法时间复杂度的多项式次数较高,以致运算效率不够高,本文利用近年来发展迅猛的并行编程技术对ZH算法进行了并行化研究,提升了ZH算法的效率。本文首先提出了一种针对一般化多项式时间算法的并行化思路,即首先确定并行代码片段,然后检视其中的数据相关性冲突并对其进行规避或是处理,最后需要对并行化方案的负载均衡以及同步点等等细节进行详细的设置,之后依照这个思路设计了ZH算法的并行化方案,并将这个方案分别移植到了PC平台与银河巨型机平台。在进一步的的工作中,本文对ZH算法的并行化方案从负载均衡、消息通信等方面进行了优化,并且针对巨型机的硬件架构特点,在巨型机中采用了节点内部多线程并行,节点外部利用消息通信机制进行并行的并行架构,最后通过实验与理论证明验证了ZH算法并行化的正确性,测试结果也表明,在PC机和巨型机上ZH算法的并行化能够有较好的加速比。