Computer Engineering and Applications ›› 2017, Vol. 53 ›› Issue (9): 47-50.DOI: 10.3778/j.issn.1002-8331.1511-0190

Previous Articles     Next Articles

Weighted path matrix of graph and all pairs shortest path problem

GAO Zunhai, GAO Ying, CHENG Guo   

  1. School of Mathematics and Computer Science, Wuhan Polytechnic University, Wuhan 430023, China
  • Online:2017-05-01 Published:2017-05-15


高遵海,高  颖,程  果   

  1. 武汉轻工大学 数学与计算机学院,武汉 430023

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

摘要: 给出了二维元素矩阵的概念,对于赋权图对应的赋权矩阵,定义了二维元素初始赋权路径矩阵和二维元素一般赋权路径矩阵,在通常赋权矩阵“乘法”运算基础上定义了路径“乘法”运算,从而得到了二维元素一般赋权路径矩阵的“乘法”运算,通过其“乘法”运算来求出所有点对的最短距离与对应路径,在得到最短距离的同时也得到对应的路径,结果显示在最终的一般赋权路径矩阵上。该算法易于通过计算机编程实现,对于大规模有向图或无向图,更有优势。

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