下圖給出了乙個地圖，地圖中每個頂點代表乙個城市，兩個城市間的連線代表道路，連線上的數值代表道路長度。
現在，我們想從城市a到達城市e。怎樣走才能使得路徑最短，最短路徑的長度是多少？設
dis［x］為城市x到城市e的最短路徑長度（x表示任意乙個城市）；
map[i，j]表示i，j兩個城市間的距離，若map[i，j]=0，則兩個城市不通；
我們可以使用回溯法來計算dis［x］：
vars：末訪問的城市集合；
function search(who)：integer求城市who與城市e的最短距離}
begin
if who＝e then search←0
else begin
min←maxint；
for i取遍所有城市do
if（map[who，i]＞0）and（is）
then begin
s←s－[i城市i已訪問}
j←map[who，i]+ search(i計算城市e至城市who的路徑長度}
s←s＋[i恢復城市i未訪問狀態}
if j＜min then min←j若城市e至城市who的路徑長度為目前最短，則記下}
end；
search←min返回城市e至城市的最短路徑長度}
end；
end；
begin
s←除e外的所有城市；
dis[a]←search（a計算城市a到城市e的最短路徑長度}
輸出dis[a]；
end．
這個程式的效率如何呢？我們可以看到，每次除了已經訪問過的城市外，其他城市都要訪問，所以時間複雜度為o（n！），這是乙個「指數級」的演算法。那麼，還有沒有效率更高的解題方法呢？
首先，我們來觀察上述演算法。在求b1到e的最短路徑的時候，先求出從c2到e的最短路徑；而在求從b2剄e的最短路徑的時候，又求了一遍從c2剄e的最短路徑。也就是說，從c2到e的最短路徑求了兩遍。
同樣可以發現，在求從cl、c2剄e的最短路徑的過程中，從dl到e的最短路徑也被求了兩遍。而在整個程式中，從dl到e的最短路徑被求了四遍，這是多麼大的乙個浪費啊！如果在求解的過程中，同時將求得的最短路徑的距離「記錄在案」，以便將來隨時呼叫，則可以避免這種重複計算。
至此，乙個新的思路產生了，即
由後往前依次推出每個dis值，直到推出dis「a」為止。
問題是，究竟什麼是「由後往前」呢？所謂前後關係是指對於任意一對城市i和j來說，如果滿足「或者城市i和城市j不連通或者dis[i]+map[i，j]≥dis[j]」的條件，則定義為城市i在前、城市j在後。因為如果城市i和城市j連通且dis[i]＋map[i，j]＜dis「j」，則說明城市j至城市e的最短路徑長度應該比dis[j]更優。
可城市j位於城市i後不可能推出此情況，以至於影響最後的解。那麼，我們應該如何劃分先後次序呢？
如上圖所示，從城市a出發，按照與城市a的路徑長度劃分階段。
階段0包含的出發城市有
階段1所含的城市有
階段2包含的出發城市有
階段3包含的出發城市有
階段4包含城市
這種劃分可以明確每個城市的次序，因為階段的劃分具有如下性質
⑴階段i的取值只與階段i+1有關，階段i+1的取值只對階段i的取值產生影響：
⑵每個階段的順序是確定的，不可以調換任兩個階段的順序；
我們從階段4的城市e出發，按照階段的順序倒推至階段0的城市a。在求解的各個階段，利用了k階段與k+1階段之間的如下關係
dis[k][x]=
dis[4][e]=0
k=4，3…，0，其中dis[k][x]指k階段的城市x。由此得出程式
dis[e]←0；
for k←3 downto 0 do
for x取遍k階段的所有城市do
begin
dis[x]←∞；
for y取遍k+1階段的所有城市do if dis[y]+map[x,y] end；
輸出dis[a]；
這個程式的時間複雜度為w(n2)，比回溯法的時間複雜度o（n!）要小得多，其解題的思路就是本章要講的動態程式設計方法。
最短路徑問題 專題
初中數學中最短路徑問題雖然只是乙個課題學習，但它在中學數學中的地位很重要，是大考 小考 競賽中經常涉及的乙個考點。所以我們要對它有足夠的重視。初中最短路徑問題主要針對軸對稱圖形考慮的。那麼只要涉及軸對稱圖形就有可能產生最短路徑問題。在此之前，我們接觸過的最短距離問題是 1 兩點間直線段最短 2 點到...
動態規劃最短路徑問題
首先，我們來觀察上述演算法。在求b1到e的最短路徑的時候，先求出從c2到e的最短路徑 而在求從b2剄e的最短路徑的時候，又求了一遍從c2剄e的最短路徑。也就是說，從c2到e的最短路徑求了兩遍。同樣可以發現，在求從cl c2剄e的最短路徑的過程中，從dl到e的最短路徑也被求了兩遍。而在整個程式中，從d...
最短路徑動態規劃問題及其程式設計
摘要 以最短路徑問題為例，在給出佛洛伊德演算法的基礎上，設計了求解該演算法的計算程式，這樣可大大提高最短路徑計算的效率。關鍵字 最短路徑，動態規劃，程式設計 1佛洛伊德演算法 2.動態規劃求解的佛洛伊德演算法程式設計 如下圖所示 給定乙個線路網路，兩點之間連線上的數字表示兩點間的距離，求一條從a到e...