問題描寫叙述:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLi8CXxAzN3ITM1EzX19CXt92Yu8GdjFTNuc2bsJ2Lc9CX6MHc0RHaiojIsJye.jpg)
上述問題能夠使用動态規劃的方法來解決。
以下是解決思路的詳細介紹:
1. 最優子結構:
如果d[i][j]表示從起點1出發到達i及j兩個頂點的最短路程之和。
為此能夠如果K為此段路程上與j相加的節點。則d[i][j] = d[i][k] + len[k][j]。
證明:若存在一個更短的路徑d[i][k],則就應該存在更短的路徑d[i][j]。這與如果沖突,是以得證。
以下來尋找j相鄰的節點,當中若i<j-1,則顯然k=j-1,若i=j-1。則顯然k屬于(1,j-2)之間。為此得到例如以下的遞推關系:
d[i][j] = d[i][j-1]+len(j,j-1) i<j-1;
d[i][j] = min(d[i][k] + len(k,j)),k屬于(1,j-2)。
終于輸出的d[n-1][n]就可以。
對于路徑的輸出,僅僅須要記錄每次與j相鄰的節點就可以,也即記錄k的值。
詳細實作稍後補充!!