一个O（n 3 ）多项式时间算法解决有向图次短路问题

发布时间：2021-04-10 04:35

　　给定一个正权重有向图D=（V, A; w; s, t）,其中s,t是有向图D中的两个固定顶点,w:A→R+是有向图D中弧的长度函数;最短路是指有向图中所有路长度最小者,次短路是指长度比最短路严格大的所有路中的最小者;利用有向图中最短路算法与最小费用流算法研究有向图中次短路问题,在s-t最短路有向图Dst=（Vst, Ast; w; s, t）上求解次短路,并设计一个O（n3）多项式时间算法解决正权重有向图的次短路问题。 

【文章来源】：保山学院学报. 2020,39(05)

【文章页数】：3 页


本文编号：3128971