Of Method On The Shortest Path Based On Pvm

The problem of shortest path is very common in computer graph theory, when count the shortest path of a graph, we usually count the length of all different paths, then chose the shortest one. The computational amount is very big. And if you want to know all the shortest paths, the times of count is amazing.When solving the problem of shortest path, we can use matrix to solve the connectivity between nodes and the number of articles in the particular length under the pathway. In this paper, by changing the matrix multiplication algorithm, we can find all shortest paths between nodes. During the produce of solve the problem we employ parallel program under the PVM, by limit the sum of processes to improve the program efficiency.The main works of this paper is outlined as follows:1. Summarize the history of parallel compute, the research background and importance of the problem and the main works of this paper.2. Detailed state the basic principle of parallel computer design, pattern of program, basic technology of parallel computer and the appraisal standard of the parallel program.3. Illustrate how to choose the serial program and parallel program.4. Build the programming environment-PVM, illustrate two different modes of programming, and how to choose them.5. By changing the matrix multiplication algorithm, we can find all shortest paths between nodes by the form of matrix multiplication.6. Realize the algorithm under the programming environment-PVM, improve the program's efficiency by limit the total of processes.Finally, the problems still exiting and the future research direction were summarized, and the prospect of this paper was elaborated.