本文轉載本人獨立博客：http://zhexue.sinaapp.com/?p=13
最短路徑問題，一個經典算法問題。本文粗略總結了一種常見的最短路徑算法，以及幾個最短路徑變種問題的解法，其中包括哈密頓路。對于有向圖或者無向圖，假設有V個節點，E條邊，G[Vi,Vj]表示圖中點Vi到Vj邊的權值。dist[i]表示：點s到點i的最短路徑。
一、單源最短路徑
給定圖G，求點對s->t之間的最短路徑，該問題使用經典的dijkstra算法即可解決，時間復雜度O(V^2)。基本思想：兩個集合S,T，S表示已經訪問的點集合，T表示未訪問的點集合，S初始為空，T包括所有點；每次從T集合中選取從s到該點距離最小的點cur，然后將點cur加入到S中（保證從s到S集合中的點之間的路徑長度最小），并且基于cur點為跳板，做松弛操作，更新s到T集合中其他點的距離，松弛操作即，如果dist[j] > dist[cur] + G[cur,j]，更新dist[j] = dist[cur]+G[cur,j]，其中j屬于T集合；當cur==t時算法結束。
dijkstra代碼下載
二、有負權邊的圖的單源最短路徑
對于（一）中的dijkstra算法，是否可以用于求解帶負權邊的單源最短路徑問題呢？用三元組(x,y,w)表示一條邊權為w的從點x到點y的有向邊。先舉例看看，假設圖中包含3個節點，包含3條邊：（1，2，-3）、（2，3，1）、（3，1，1），從圖可以看出為一個環1->2->3->1，且環的邊權總權值為-3+1+1=-1，那么通過一直循環，那么圖中任意兩點之間的最短路徑都為-oo大，因此不能通過dijkstra來求解最短路徑，因為出現負環之后破壞了“從s到集合S中點之間路徑長度最小”這點，通過負環的循環，s到S中點之間的路徑長度還可以變小。
對付有負權邊的單源最短路徑問題，可以采用bellman-ford算法、SPFA算法。
Bellman-ford算法思想：dist[s] = 0,其他點i ,dist[i]=oo。進行V-1次循環，每一次循環：對圖每一條邊E(i,j)兩邊的點做松弛操作，如果dist[j] > dist[i] + G[i,j]，更新dist[j] = dist[i]+G[i,j]。完成V-1次循環后，進行判斷：如果存在一條邊E(i,j)，如果dist[i]+G[i,j] < dist[j]，那么圖中存在負權環。如果不存在負權環，則dist[t]為從s到t的最短路徑。算法復雜度O(VE)。
Bellman-ford算法代碼下載
SPFA算法思想：維護一個隊列Q，隊列初始只有s點，一個標記數組flag，flag[i]=1表示節點i在隊列中，否則表示不在隊列中，一個cnt數組，cnt[i]標記點i進入隊列的次數。求隊首元素cur，對于邊E(cur,j)，進行松弛操作：如果dist[j] > dist[cur] + G[cur,j]，更新dist[j] = dist[cur]+G[cur,j]，如果j不在隊列中，則將j加入隊尾，同時判斷j進入隊列次數是否大于V-1，如果大于V-1，說明存在負權環，算法結束，否則一直進行，直到隊列為空為止。算法復雜度O(2E)。
SPFA算法代碼以及論文下載
三、大規模的圖，頂點多的稀疏圖
Dijkstra算法復雜度為O(V^2)，如果圖的規模太大，那么無疑難以勝任。其實，對與規模大的圖，可以使用min-heap優化，復雜度O((V+E)logV)。思想：維護一個最小堆，用于優化Dijkstrak中從T選取從s到T中路徑最短的點，該點即堆頂元素。這個方法即A*搜索。
Dijkstra+heap代碼下載
四、全源最短路徑問題
全源最短路徑即求出圖中任意點對之間的最短路徑。方法（1）：枚舉任意點對，采用dijkstra算法求解即可，復雜度O(V^4)。方法（2）：以每一個點為松弛操作的中間點，枚舉其他兩點，進行松弛操作，即可得到全源最短路徑，這便是鼎鼎大名的floyd算法，其狀態轉移方程如下： G[i,j]=min{G[i,k]+G[k,j],G[i,j]}，時間復雜度O(V^3)。
floyd算法代碼下載
五、最短哈密頓路徑
從s出發到達t，且經過圖中每個點至少一次的最短路徑長度。這個問題是一個NPC問題，沒有高效的解法。假設有N個點，那么N位bit來標記那些點已經訪問過，哪些沒有訪問過。設f[I][J]表示，從s出發達到J，且經過了I中對應位標記為1的所有點的最短路徑。有方程如下：
f[I1][J1] = min{F[I][J] + G[J][j], 枚舉I,J,j,其中(I&(1<<j)) == 0 && (I|(1<<j) )== I1 && (I&(1<<J)) != 0}
初始只f[(1<<s)][s] = 0， 從改點出發，利用上述方程推出所有的中間變量，包括結果f[(1<<V)-1][t]。下面代碼用于求解小規模圖的哈密頓路。
代碼下載
六、第K短路徑問題
求s到t的第k短路徑，如果k=1，直接采用dijkstra算法即可求解。如果k=2的話，首先采用dijkstra算法求解最短路徑，然后枚舉刪除最短路徑上邊，再次進行dijkstra算法，求解最短路徑即為第k短路徑。
理論一：A*算法求解到的路徑是最短的。
根據理論一就可以用A*路徑求得最短路徑，比dijkstra盲目式算法效率高。
假設用A*算法求得最短路徑時，即第一次搜索到目標節點后不停止。繼續啟發式搜索下去，那么根據理論一可以得到第二次搜索到目標節點的路徑是第二短路徑。依次類推得到第k短路徑。
那么A*算法的h’（x）怎么設計呢？
已知h’（x）與h（x）越接近，時間效率越好，h（x）為x到目標節點的實際最短路長。既然這樣那么直接取最好值，先用dijkstra算法算出各點到目標節點的最短路徑作為估價值h’（x），使效率到達極大。
第K短路徑代碼下載