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

Matrix method of detecting negative cycle in negative weighted shortest path

作　　者：高遵海[1] 杨波[1] 程果[1] GAO Zun-hai YANG Bo CHENG Guo(School of Mathematics and Computer Science, Wuhan Polytechnic University, Wuhan 430023, Chin)

机构地区：[1]武汉轻工大学数学与计算机学院,湖北武汉430023

出　　处：《计算机工程与设计》2016年第11期3012-3015,共4页Computer Engineering and Design

基　　金：国家自然科学基金项目(61179032;11301405)

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

关 键 词：有向图 负环 最短路径 赋权路径矩阵 赋权路径矩阵乘法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]