步驟(1)、(2)已實現。
最優子結構：從起點到終點的最短路徑包含了該路徑上各點到終點的最短路徑。
遞迴公式：設v為圖中乙個頂點，v1, v2,…, vm為v的直接後繼，cost(v)表示v到終點的最短路徑長度，c[u, w]表示邊上的權，t為終點，則cost滿足如下遞迴公式：
步驟(3) 計算最優值（求最短路徑長度）：
設有向網g含n個頂點，用鄰接矩陣c[1..n, 1..n]表示，起點為s，終點為t 。
有關資訊的儲存：
陣列cost[1..n]: 儲存子問題的解。
cost[i]表示從頂點i到終點t的最短路徑長度。）
陣列succ[1..n]: 儲存最短路徑的有關資訊。
succ[i]表示頂點i到終點t的最短路徑上頂點i的直接後繼。）
原問題的最優值為cost[s]。
(1) 自底向上的迭代演算法
關鍵：根據遞迴公式確定迭代順序（即子問題的求解順序）。
原則：計算cost[i]時，頂點i的所有後繼的cost值應先計算。
計算順序：按圖g的逆拓撲排序順序。
演算法 shortest_route_len1
輸入：有向網g的頂點數n, 鄰接矩陣c[1..n, 1..n], 起點s和終點t , 1<=s, t<=n。
輸出：g的從起點s到終點t的最短路徑長度cost[s]和最短路徑有關資訊的陣列succ[1..n]。
對圖g拓撲排序， 結果存於陣列a[1..n]中。
toposort(c, n, a)
j=nwhile a[j]< >t j=j-1 //找出j使得a[j]=t 。
for i=j+1 to n cost[a[j]]=∞ //排除無關的頂點。
cost[t]=0 //從終點開始迭代。
while a[j]< >s
j=j-1; k=a[j]; i0=0 ; min=∞
for i=1 to n
if c[k, i]+cost[i] i0=i; min=c[k, i]+cost[i]
end if
end for
cost[k]=min ; succ[k]=i0
end while
end shortest_route_len1
(2) 自頂向下的遞迴演算法
關鍵：對每個子問題標記是否計算過，同一子問題只在第一次遞迴呼叫時計算並儲存結果。
標記：未求出cost[i]時，cost[i]=-1 。
演算法 shortest_route_len2
輸入：有向網g的頂點數n, 鄰接矩陣c[1..n, 1..n], 起點s和終點t , 1<=s, t<=n。
輸出：g的從起點s到終點t的最短路徑長度minlen和最短路徑有關資訊的陣列succ[1..n]。
for i=1 to n cost[i]=-1
minlen=routelength(s)
end shortest_route_len2
過程 routelength( j )
// 求g中從頂點j到終點t的最短路徑長度cost[j]並返回，//同時求該路徑上各頂點的直接後繼存於陣列succ中。
if cost[j]=-1 then //cost[j]還未求出
if j=t then cost[j]=0
else
min=∞ ; i0=0
for i=1 to n
if c[j, i]< ∞ then //頂點i為頂點j的後繼
x=routelength( i ) //求i到t的最短路徑長度
if c[j, i]+x min=c[j, i]+x; i0=i
end if
end if
end for
cost[j]=min; succ[j]=i0;
end if
end if
return cost[j]
end routelength
步驟(4) 構造最優解(設存在從起點s到終點的路徑)
演算法 shortest_route
輸入：有向網g的從起點s到終點t的最短路徑資訊陣列succ[1..n]
輸出: 有向網g的從起點s到終點t的最短路徑。
i=1; b[i]=s
while b[i]< >t
b[i+1]=succ[b[i]]
i=i+1
end while
輸出b[1..i]
end shortest_route
最壞情況下時間複雜性：
演算法 shortest_route_len1（或2）：θ(n2)
演算法 shortest_route：θ(n)
動態規劃最短路徑問題
首先，我們來觀察上述演算法。在求b1到e的最短路徑的時候，先求出從c2到e的最短路徑 而在求從b2剄e的最短路徑的時候，又求了一遍從c2剄e的最短路徑。也就是說，從c2到e的最短路徑求了兩遍。同樣可以發現，在求從cl c2剄e的最短路徑的過程中，從dl到e的最短路徑也被求了兩遍。而在整個程式中，從d...
最短路徑動態規劃問題及其程式設計
摘要 以最短路徑問題為例，在給出佛洛伊德演算法的基礎上，設計了求解該演算法的計算程式，這樣可大大提高最短路徑計算的效率。關鍵字 最短路徑，動態規劃，程式設計 1佛洛伊德演算法 2.動態規劃求解的佛洛伊德演算法程式設計 如下圖所示 給定乙個線路網路，兩點之間連線上的數字表示兩點間的距離，求一條從a到e...
最短路徑問題 專題
初中數學中最短路徑問題雖然只是乙個課題學習，但它在中學數學中的地位很重要，是大考 小考 競賽中經常涉及的乙個考點。所以我們要對它有足夠的重視。初中最短路徑問題主要針對軸對稱圖形考慮的。那麼只要涉及軸對稱圖形就有可能產生最短路徑問題。在此之前，我們接觸過的最短距離問題是 1 兩點間直線段最短 2 點到...