給定一個正權(quán)重有向圖D=（V, A; w; s, t）,其中s,t是有向圖D中的兩個固定頂點,w:A→R+是有向圖D中弧的長度函數(shù);最短路是指有向圖中所有路長度最小者,次短路是指長度比最短路嚴格大的所有路中的最小者;利用有向圖中最短路算法與最小費用流算法研究有向圖中次短路問題,在s-t最短路有向圖Dst=（Vst, Ast; w; s, t）上求解次短路,并設(shè)計一個O（n3）多項式時間算法解決正權(quán)重有向圖的次短路問題。 

【文章來源】：保山學(xué)院學(xué)報. 2020,39(05)

【文章頁數(shù)】：3 頁


本文編號：3128971