关键词: 最短路径问题, 二维元素矩阵, 赋权路径矩阵, 赋权路径矩阵乘法

Abstract: The concept of two-dimensional element matrix is presented. For the weighted matrix corresponding to a weighted graph, the two-dimensional element initial weighted path matrix and general weighted path matrix are defined. Based on the general multiplication operation of the weighted matrices, the multiplication operation of the paths is defined,  and then the multiplication operation of the general weighted path matrices is derived,  by which all the minimum weights and all the shortest paths of all pairs can be found clearly in the final general weighted path matrix.  This algorithm is easy to be realized by computer program.  It is more intuitive and will not miss any path for large-scale directed graph or undirected graph.

Key words: shortest path problem, two-dimensional elements matrix, weighted path matrix, multiplication of weighted path matrix