网络中含有负圈的最短路径问题

网络中含有负圈的最短路径问题 THE SHORTEST PATH PROBLEM IN A NETWORK CONTAINING NEGATIVE CYCLES 莫忠息 Mo Zhongxi 1 first-author 武汉大学数学系 武汉大学数学系 Department of Mathematics, Wuhan University Department of Mathematics, Wuhan University 本文讨论了网络中含有负圈的最短路径问题.基于结点标号深度的概念,给出了一个具有"尖利"性质的求其近似最优解的算法——避负圈法。 This paper discusses the shortest path problem in a network containing cycles with nega- tive lengths,which is an NP-Complete problem. Based on the concept of the node label depth, a polyno- mially bounded sharp algorithm, called the evading negative cycle method, for finding an approximate- ly optimal solution of this problem is developed, and a strategy to improve the approximate solution is presented. 网络 负圈 最短路径 有向树 network negative cycle shortest path directed tree O157.5 1993-05-01 2021-04-01 5