一个O(n3)多项式时间算法解决有向图次短路问题  

An Algorithm with Time Complexity O(n3)Solving the Next-to-short⁃est Path Problem in Directed Graph

作　　者：曾庆红 杨桥艳 Zeng Qinghong;Yang Qiaoyan(School of Mathematics,Baoshan University,Baoshan Yunnan 678000)

机构地区：[1]保山学院数学学院,云南保山678000

出　　处：《保山学院学报》2020年第5期36-38,共3页JOURNAL OF BAOSHAN UNIVERSITY

基　　金：云南省教育厅研究项目“路径问题算法研究”(项目编号:2019J0334)。

摘　　要：给定一个正权重有向图D=(V,A;w;s,t),其中s,t是有向图D中的两个固定顶点,w:A→R+是有向图D中弧的长度函数;最短路是指有向图中所有路长度最小者,次短路是指长度比最短路严格大的所有路中的最小者;利用有向图中最短路算法与最小费用流算法研究有向图中次短路问题,在s-t最短路有向图Dst=(Vst,Ast;w;s,t)上求解次短路,并设计一个O(n3)多项式时间算法解决正权重有向图的次短路问题。Given an directed graph,where are two fixed vertices in directed graph D,and w:A→R+is the length function in directed graph D.The shortest path is a path having the minimum length of all paths in directed graph,the next-to-shortest path is a shortest path amongst all paths having length strictly greater than the length of a shortest path.This paper combines the shortest path algorithm with the minimum cost flow algorithm to study the next-to-shortest path problem in the directed graph,find the next-to-shortest path on s-t shortest path directed graph Dst=(Vst,Ast;w;s,t)and proposes an algo⁃rithm with time complexity O(n3)to solve the next-to-shortest path problem in directed graph with posi⁃tive weight.

关 键 词：最短路 次短路 最小费用流 算法 

分 类 号：O13[理学—数学]