任意兩點間最短路問題及路徑還原

考慮用動态規劃的方法，隻使用頂點0~k和i，j的情況下，記i到j的最短路徑為d[k][i][j]。當k=0時，隻考慮i和j，即d[0][i][j]=cost[i][j].然後我們就開始讨論從k到k+1是怎樣變化的。

對于頂點0~k的i到j的最短路，如果這條路徑不經過第k個頂點，那麼d[k][i][j]=d[k-1][i][j]。當經過第k個頂點時，d[k][i][j]=d[k-1][i][k]+d[k-1][k][j](分成兩短)，這樣總的遞推式即為d[k][i][j]=min(d[k-1][i][j]+d[k-1][i][k]+d[k-1][k][j]).

由于是三維數組，每層都要周遊所有節點，是以複雜度為o(|v|^3)。

代碼如下

本文和上篇部落格讨論了如何求最短路徑，但未能還原出最短路徑是怎麼走的。

思路如下：我們需要找到滿足d[j]=d[k]+cost[k][j]的頂點k，他是最短路上j前面的點，不斷尋找就能找到最短路，時間複雜度為o（|e|）。

如果我們用一個數組記錄這個點prev[j]=k，那麼時間複雜度就變為o（|v|）。

給出dijkstra算法的代碼作為參考：