图的赋权路径矩阵与所有点对最短路径问题

摘要：

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

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

所属期刊栏目：53

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金61179032,11301405

在线出版日期：2017-05-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：47-50