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

摘要

给出赋权图对应的二维元素初始赋权路径矩阵和一般赋权路径矩阵概念，定义一般赋权路径矩阵的“乘法”运算，通过其“乘法”运算得到检测含负权有向赋权图负环的方法，该方法可以求含负权有向图不含负环时任意两点之间的最短距离以及对应的最短路径，结果显示在最后的一般赋权路径矩阵上。该方法对不含负权的简单有向图或无向图也成立，能同时计算所有点对的最短距离和最短路径。实例结果表明了该算法的正确性。%For the weight matrix corresponding to a weighted graph,the two-dimensional initial weight path matrix and general weight path matrix were defined.And the multiplication operation of the general weight path matrices was derived,by which a method to detect negative cycle in negative weighted directed graph was obtained.If the graph with negative weight did not have negative cycle,this method could also be used to find all the minimum weights and all the shortest paths of all pairs clearly at the same time through the final general weight path matrix.This method was applied also to simple directed graph or undirected graph with no negative weight and found all the minimum weights and all the shortest paths of all pairs at the same time.Some examples show the validity of the method.