  Recently we submitted a paper, whose title is A New Fast Unweighted All-pairs
Shortest Path Search Algorithm Based on Pruning by Shortest Path Trees, to
arXiv. This is related to unweighted graphs. This paper also presents a new
fast all-pairs shortest path algorithm for weighted graph based on the same
idea. In Dijkstra algorithm which is said to be fast in weighted graphs, the
average number of accesses to adjacent vertices (expressed by {\alpha}) is
about equal to the average degree of the graph. On the other hand, our
algorithm utilizes the shortest path trees of adjacent vertices of each source
vertex in the same manner as the algorithm for unweighted graphs, and reduce
{\alpha} drastically in comparison with Dijkstra algorithm. Roughly speaking
{\alpha} is reduced to the value close to 1, because the average degree of a
tree is about 2, and one is used to come in and the other is used to go out,
although that does not hold true when the depth of the short path trees is
small. In case of weighted graphs, a problem which does not occur in unweighted
graphs occurs. It is waiting for the generation of the shortest path tree of an
adjacent vertex. Therefore, it is possible that a deadlock occurs. We prove our
algorithm is deadlock-free. We compared our algorithm with Dijkstra and Peng
algorithms. On Dijkstra algorithm ours outperforms it on speed and {\alpha}
except that Dijkstra algorithm slightly outperforms ours or they are almost the
same on CPU time in sparse scale-free graphs. The result on Peng algorithm is
as follows: In speed and {\alpha}, ours outperforms Peng algorithm in
hypercube-shaped and dense scale-free graphs, but conversely Peng algorithm
outperforms ours in sparse scale-free graphs.
