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

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

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


本文編號(hào)：3128971