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

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

有向图负环检测的负权最短路径矩阵算法

给出赋权图对应的二维元素初始赋权路径矩阵和一般赋权路径矩阵概念,定义一般赋权路径矩阵的"乘法"运算,通过其"乘法"运算得到检测含负权有向赋权图负环的方法,该方法可以求含负权有向图不含负环时任意两点之间的最短距离以及对应的最短路径,结果显示在最后的一般赋权路径矩阵上。该方法对不含负权的简单有向图或无向图也成立,能同时计算所有点对的最短距离和最短路径。实例结果表明了该算法的正确性。