计算机工程与应用2017，Vol.53Issue(9)：47-50,4.DOI:10.3778/j.issn.1002-8331.1511-0190
图的赋权路径矩阵与所有点对最短路径问题
Weighted path matrix of graph and all pairs shortest path problem
摘要
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 de-fined, 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 algo-rithm 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分类
信息技术与安全科学引用本文复制引用
高遵海,高颖,程果..图的赋权路径矩阵与所有点对最短路径问题[J].计算机工程与应用,2017,53(9):47-50,4.基金项目
国家自然科学基金(No.61179032,No.11301405). （No.61179032,No.11301405）
