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