最短路径问题是计算机图论中常见的问题。通常求解一个图中的最短路径都采用穷举法,要找出结点a到结点b的最短路径是通过求出结点a到结点b的各个通路的权值之和,再通过比较找出最短的一个,计算量非常大。若要求解所有点到点之间的最短路径计算量更是惊人。在求解最短路径问题时,可以利用矩阵的形式求解图中结点间的连通性以及在特定长度下结点间通路的条数。本文通过改变矩阵的运算法则,利用矩阵相乘的形式求解图中所有的点与点之间的最短路径。在问题求解过程中采用在PVM环境下的并行程序进行求解,通过对并行程序中进程数目的限制,提高程序的运行效率。本文主要工作如下：1、综述了并行计算的发展史、本文问题提出的背景、意义及论文主要的研究内容。2、具体讲述了并行计算设计基本原则、编程模型、并行算法的基本设计技术和并行程序优劣的评价标准。3、通过实例说明串行和并行的选择。4、搭建PVM并行编程平台,讲述两种主要的编程模型及两个编程模型的选择。5、通过改变矩阵的运算法则,利用矩阵相乘的形式求解图中所有点与点之间的最短路径。6、在PVM环境下实现求解最短路径的算法,通过对程序中进程数目的限制提高并行程序的运行效率。最后对文章所做工作进行总结,提出所做工作中存在的不足,对如何提高程序运行效率提出看法。