帶權(quán)圖如何選取最短的和次短的路徑？將距離作為負(fù)值是一個最短路徑問題。Dijkstra算法不適用于負(fù)權(quán)最短路徑，而BellmanFord算法和基于松弛技術(shù)的Floyd算法適用于負(fù)權(quán)最短路徑。采用Floy

帶權(quán)圖如何選取最短的和次短的路徑？

將距離作為負(fù)值是一個最短路徑問題。Dijkstra算法不適用于負(fù)權(quán)最短路徑，而BellmanFord算法和基于松弛技術(shù)的Floyd算法適用于負(fù)權(quán)最短路徑。采用Floyd算法計算多點(diǎn)間的最短路徑。具體來說，使用n-2輪放松，即對任意兩點(diǎn)耗盡第三點(diǎn)，并嘗試用通過第三點(diǎn)的距離來代替距離。如果距離繼續(xù)減小，則表示存在負(fù)權(quán)重定向環(huán)，且不存在最短路徑（可以沿圓連續(xù)），否則當(dāng)前路徑為最短路徑。然而，該圖有一個特殊的特點(diǎn)，即它的有向邊只能由小邊到大邊，這是比較簡單的。在某一點(diǎn)結(jié)束的路徑只能由數(shù)字較小的頂點(diǎn)和它們之間的邊來確定。這是一個動態(tài)規(guī)劃問題。它可以表示為：其中d[k]是以頂點(diǎn)k結(jié)束的最長路徑的長度，d（J，k）表示J和k之間的有向邊的距離，如果用一個特殊的鄰接表（反向鄰接表，邊按端點(diǎn)組織）表示，這是一個O（E）復(fù)雜度算法，最后的答案是D[k]的最大值。