最短路徑算法
單源最短路徑問題
問題描述：給你一個頂點做源點，你想要知道，如何從源點到達其他所有點的最短路徑。
OK，這個問題看起來沒什么用。我們一般想知道的是A點到B點的最短路徑，這個單源最短路徑問題告訴我們A點到所有點的最短路徑，會不會計算過多了呢？
有趣的是，解決A點到B點的最短路徑算法不會比單源最短路徑問題簡單，我們所知的求A點到B點的最短路徑算法就是求A點到任何點的最短路徑。我們除了這樣做，好像也沒什么好辦法了。
Dijkstra算法
基本原理：
每次新擴展一個距離最短的點，更新與其相鄰的點的距離。當所有邊權都為正時，由于不會存在一個距離更短的沒擴展過的點，所以這個點的距離永遠不會再被改變，因而保證了算法的正確性。不過根據這個原理，用Dijkstra求最短路的圖不能有負權邊，因為擴展到負權邊的時候會產生更短的距離，有可能就破壞了已經更新的點距離不會改變的性質。
適用條件與限制：
- 有向圖和無向圖都可以使用本算法，無向圖中的每條邊可以看成相反的兩條邊。
- 用來求最短路的圖中不能存在負權邊。(可以利用拓撲排序檢測)
算法流程：
在以下說明中，s為源，w[u,v]為點u和v之間的邊的長度，結果保存在dist[]
- 初始化：源的距離dist[s]設為0，其他的點距離設為正無窮大，同時把所有的點的狀態設為沒有擴展過。
- 循環n-1次：
- 在沒有擴展過的點中取距離最小的點u，并將其狀態設為已擴展。
- 對于每個與u相鄰（有向圖只kao慮出度）的點v，執行Relax(u,v)，也就是說，如果dist[u]+w[u,v]<dist[v]，那么把dist[v]更新成更短的距離dist[u]+w[u,v]。此時到點v的最短路徑上，前一個節點即為u。
- 結束。此時對于任意的u，dist[u]就是s到u的距離。
</ol> </li>
執行動畫過程如下圖:
實例：
用Dijkstra算法找出以A為起點的單源最短路徑步驟如下
代碼：
我們在OJ上完成這個算法：http://acm.hdu.edu.cn/showproblem.php?pid=1874
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; public class Main { static int[][] v = new int[201][201]; static int[] dist = new int[201]; static boolean[] visit = new boolean[201]; public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int n, m, begin, end; while (in.nextToken() != StreamTokenizer.TT_EOF) { n = (int) in.nval; in.nextToken(); m = (int) in.nval; init(n); for (int i = 0; i < m; i++) { in.nextToken(); int a = (int) in.nval; in.nextToken(); int b = (int) in.nval; in.nextToken(); int d = (int) in.nval; if (d < v[a][b]) { v[a][b] = d; v[b][a] = d; } } in.nextToken(); begin = (int) in.nval; in.nextToken(); end = (int) in.nval; if (begin == end) { System.out.println("0"); continue; } dist[begin] = 0; visit[begin] = true; dijkstra(begin, n); if (!visit[end]) { System.out.println("-1"); } else { System.out.println(dist[end]); } } } public static void init(int n) { for (int i = 0; i < n; i++) { visit[i] = false; for (int j = 0; j < n; j++) { v[i][j] = 10000; } } } public static void dijkstra(int s, int n) { for (int i = 0; i < n; i++) { dist[i] = v[s][i]; } for (int i = 0; i < n - 1; i++) { int min = 10000; int index = 0; for (int j = 0; j < n; j++) { if (!visit[j] && dist[j] < min) { min = dist[j]; index = j; } } visit[index] = true; for (int j = 0; j < n; j++) { if (!visit[j] && dist[index] + v[index][j] < dist[j]) { dist[j] = dist[index] + v[index][j]; } } } } }可以看出時間復雜度為 O（v^2）。有沒有更快的方法呢？由于每次都要找到未訪問的點中距離最小的點，我們使用優先隊列來解決這個問題，關于優先隊列請查看這篇Blog。以下是利用優先隊列實現的算法
public static void dijkstrapq(int s, int n) { class Item implements Comparable<Item> { public int idx; public int weight; public Item(int idx, int weight) { this.idx = idx; this.weight = weight; } @Override public int compareTo(Item item) { if (this.weight == item.weight) { return 0; } else if (this.weight < item.weight) { return -1; } else { return 1; } } } PriorityQueue<Item> pq = new PriorityQueue<Item>(); for (int i = 0; i < n; i++) { dist[i] = v[s][i]; if (i != s) { pq.offer(new Item(i, dist[i])); } } Item itm = null; while (!pq.isEmpty()) { itm = pq.poll(); int index = itm.idx; int weight = itm.weight; if (weight == 10000) { break; } visit[index] = true; for (int j = 0; j < n; j++) { if (!visit[j] && dist[index] + v[index][j] < dist[j]) { dist[j] = dist[index] + v[index][j]; pq.offer(new Item(j, dist[j])); } } } }如果是稠密圖（邊比點多），則直接掃描所有未收錄頂點比較好，即第一種方法，每次O(V)，總體算法復雜度T=O(V^2+E)如果是稀疏圖(邊比點少)，則使用優先隊列（最小堆）比較好，即第二種方法，每次O(logV)，插入更新后的dist，O(logV)。總體算法復雜度T=O(VlogV+ElogE)
當然還有更加優秀的斐波那契堆，時間復雜度為 O(e+vlogv)
無權值（或者權值相等）的單源點最短路徑問題，Dijkstra算法退化成BFS廣度優先搜索。
那么，為什么BFS會比Dijkstra在這類問題上表現得更加好呢？
1. BFS使用FIFO的隊列來代替Dijkstra中的優先隊列(或者heap之類的)。
2. BFS不需要在每次選取最小結點時判斷其他結點是否有更優的路徑。
BFS的時間復雜度為O(v+e)
Bellman-Ford算法
Dijkstra很優秀，但是使用Dijkstra有一個最大的限制，就是不能有負權邊。而Bellman-Ford適用于權值可以為負、無權值為負的回路的圖。這比Dijkstra算法的使用范圍要廣。其基本思想為：首先假設源點到所有點的距離為無窮大，然后從任一頂點u出發，遍歷其它所有頂點vi，計算從源點到其它頂點vi的距離與從vi到u的距離的和，如果比原來距離小，則更新，遍歷完所有的頂點為止，即可求得源點到所有頂點的最短距離。
Bellman－Ford算法可以大致分為三個部分
- 第一，初始化所有點。每一個點保存一個值，表示從原點到達這個點的距離，將原點的值設為0，其它的點的值設為無窮大（表示不可達）。
- 第二，進行循環，循環下標為從1到n－1（n等于圖中點的個數）。在循環內部，遍歷所有的邊，進行松弛計算。
- 第三，遍歷途中所有的邊（edge（u，v）），判斷是否存在這樣情況：d（v） > d (u) + w(u,v)。則返回false，表示途中存在從源點可達的權為負的回路。
對有向帶權圖G = (V, E)，從頂點s起始，利用Bellman-Ford算法求解各頂點最短距離，算法描述如下：
for(int k=1;k<=n-1;k++)//遍歷點的次數 { for(int i=1;i<=m;i++)//遍歷邊的次數 { if(dis[v[i]]>dis[u[i]]+w[i])//如果從u到v的距離能夠通過w這條邊壓縮路徑 就要進行松弛操作 { dis[v[i]]=dis[u[i]]+w[i]; } } }很明顯Bellman-Ford算法復雜度為O(VE)，比Dijkstra要慢，但是解決了負權值問題。
圖解：
當然不用總是松弛E次，可能遠小于E次時，所有邊都不能松弛了。所以加個check來優化，如果每個邊都沒松弛，就break。
for(int k=1;k<=n-1;k++) { check=0;//用check檢查是否進行下一輪次的操作 for(int i=1;i<=m;i++) { if(dis[v[i]]>dis[u[i]]+w[i]) { dis[v[i]]=dis[u[i]]+w[i]; check=1; } } if(check==0)break; }我們一直說的是有向圖的松弛，如果是無向圖則要松弛兩次（因為A到B有邊，那么B到A也有邊）
for(int k=1;k<=n-1;k++) { check=0; for(int i=1;i<=m;i++) { if(dis[v[i]]>dis[u[i]]+w[i]) { dis[v[i]]=dis[u[i]]+w[i]; check=1; } if(dis[u[i]]>dis[v[i]]+w[i]) { dis[u[i]]=dis[v[i]]+w[i]; check=1; } } if(check==0)break; }代碼：
我們在OJ上驗證這個算法：http://acm.hdu.edu.cn/showproblem.php?pid=2544
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; public class Main { static int[] begin = new int[121212]; static int[] end = new int[121212]; static int[] wight = new int[121212]; static int[] dist = new int[121212]; public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int n, m; while (in.nextToken() != StreamTokenizer.TT_EOF) { n = (int) in.nval; in.nextToken(); m = (int) in.nval; init(n); if (n == 0 || m == 0) { break; } for (int i = 1; i <= m; i++) { in.nextToken(); int a = (int) in.nval; in.nextToken(); int b = (int) in.nval; in.nextToken(); int d = (int) in.nval; begin[i] = a; end[i] = b; wight[i] = d; if (a == 1) { dist[b] = d; } if (b == 1) { dist[a] = d; } } bellmanFord(n, m); System.out.println(dist[n]); } } private static boolean bellmanFord(int n, int m) { dist[1] = 0; int check; for (int i = 1; i <= n - 1; i++) { check = 0; for (int j = 1; j <= m; j++) { int b = begin[j]; int e = end[j]; if (dist[b] + wight[j] < dist[e]) { check = 1; dist[e] = wight[j] + dist[b]; } if (dist[e] + wight[j] < dist[b]) { check = 1; dist[b] = wight[j] + dist[e]; } } if (check == 0) { break; } } return true; } public static void init(int n) { for (int i = 1; i <= n; i++) { dist[i] = 9999999; } } }OJ上的這個題目沒有負值環，Bellman-Ford是可以檢查負值環的，就如上面所說，最后再遍歷一遍邊，如果還能松弛，說明有負值環。for (int j = 1; j <= m; j++) { int b = begin[j]; int e = end[j]; if (dist[b] + wight[j] < dist[e]) { return false; } if (dist[e] + wight[j] < dist[b]) { return false; } }SPFA算法
SPFA（Shortest Path Faster Algorithm）（隊列優化）算法是求單源最短路徑的一種算法，它還有一個重要的功能是判負環（在差分約束系統中會得以體現），在Bellman-ford算法的基礎上加上一個隊列優化，減少了冗余的松弛操作，是一種高效的最短路算法。SPFA算法維護一個隊列，里面存放所有需要進行迭代的點。初始時隊列中只有一個點S。用一個布爾數組記錄每個點是否處在隊列中。
SPFA算法可以分為大致3步
- 初始化階段除了和Bellman-ford算法相同的地方外，還要加上將源點S入隊，并且在判斷點是否在隊列中的數組上做標記（inside[1] = 1）
- 進行迭代，每次迭代，取出隊頭的點v，遍歷所有與v相連的邊，進行松弛操作，如果能夠松弛并且該點不在隊列中，就將它放入隊尾。這樣一直迭代下去直到隊列變空。
- 若一個點入隊次數超過n，則有負權環。
SPFA 在形式上和寬度優先搜索非常類似，不同的是寬度優先搜索中一個點出了隊列就不可能重新進入隊列，但是SPFA中一個點可能在出隊列之后再次被放入隊列，也就是一個點改進過其它的點之后，過了一段時間可能本身被改進，于是再次用來改進其它的點，這樣反復迭代下去。
代碼：
我們在OJ上驗證這個算法：http://acm.hdu.edu.cn/showproblem.php?pid=2544
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.LinkedList; import java.util.Queue; public class Main { static int[][] v = new int[101][101]; static int[] dist = new int[101]; static int[] inside = new int[101]; static Queue<Integer> queue; public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int n, m; while (in.nextToken() != StreamTokenizer.TT_EOF) { n = (int) in.nval; in.nextToken(); m = (int) in.nval; init(n); if (n == 0 || m == 0) { break; } for (int i = 1; i <= m; i++) { in.nextToken(); int a = (int) in.nval; in.nextToken(); int b = (int) in.nval; in.nextToken(); int d = (int) in.nval; v[a][b] = d; v[b][a] = d; } SPFA(n); System.out.println(dist[n]); } } private static void SPFA(int n) { queue.add(1); inside[1] = 1; dist[1] = 0; while (!queue.isEmpty()) { int top = queue.poll(); inside[top] = 0; for (int i = 1; i <= n; i++) { if (v[top][i] < 9999999) { if (dist[top] + v[top][i] < dist[i]) { dist[i] = dist[top] + v[top][i]; if (inside[i] == 0) { queue.add(i); inside[i] = 1; } } } } } } public static void init(int n) { for (int i = 1; i <= n; i++) { dist[i] = 9999999; inside[i] = 0; for (int j = 1; j <= n; j++) { v[i][j] = 9999999; } } queue = new LinkedList<Integer>(); } }由于上述代碼使用鄰接矩陣來存儲，所以在遍歷與某點相連的邊時，復雜度較高。如果將其改成鄰接表來實現會更加明顯。在平均情況下，SPFA算法的期望時間復雜度為O(E)。但是這一說法有爭議，在這里就不討論了，總之SPFA是一種Bellman-Ford算法的優化。
多源最短路徑問題
我們已經介紹了3種解決單源最短路徑問題的算法，那么多源最短路徑問題該怎么解決呢？
很明顯有一種方法就是，將單源最短路徑問題使用N次，那么使用普通的Dijkstra算法的時間復雜度為T=O(V^3+V*E)，對于稀疏圖的效果比較好。
而第二種方法則是要介紹的Floyd算法，它的時間復雜度為T=O(V^3)，對于稠密圖來說效果更好。
Floyd算法
對于最短路徑算法來說，其重點都是松弛。由于現在是多源最短路徑問題，以前單源把dist[i]作為源點S到i的最短路徑，現在源點不單一了，所以直接表示成e(i,j)表示i到j的最短路徑。
我們已經知道松弛的原因是，有了第三個點為過渡點，使得距離變小了。
Floyd算法運用動態規劃的思想通過考慮最佳子路徑來得到最佳路徑
而Floyd算法的步驟就分為以下兩步
- 初始化：從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，或者無窮大，如果兩點之間沒有邊相連。
- 松弛：對于每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。
思想非常簡單，簡單來說就是遍歷所有的頂點，看看這個頂點是否能讓任意兩個頂點松弛。
核心代碼：
for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (v[i][k] + v[k][j] < v[i][j]) { v[i][j] = v[i][k] + v[k][j]; } } } }代碼：
我們在OJ上驗證這個算法：http://acm.hdu.edu.cn/showproblem.php?pid=2544
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; public class Main { static int[][] v = new int[101][101]; public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int n, m; while (in.nextToken() != StreamTokenizer.TT_EOF) { n = (int) in.nval; in.nextToken(); m = (int) in.nval; init(n); if (n == 0 || m == 0) { break; } for (int i = 1; i <= m; i++) { in.nextToken(); int a = (int) in.nval; in.nextToken(); int b = (int) in.nval; in.nextToken(); int d = (int) in.nval; v[a][b] = d; v[b][a] = d; } floyd(n); System.out.println(v[1][n]); } } private static void floyd(int n) { for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (v[i][k] + v[k][j] < v[i][j]) { v[i][j] = v[i][k] + v[k][j]; } } } } } public static void init(int n) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { v[i][j] = 9999999; } } } }算法時間復雜度很直觀O(V^3)，因為要用鄰接矩陣來存儲圖，空間復雜度O(V^2)。另外需要注意的是：Floyd算法也不能解決帶有“負權回路”
總結：
通過以上4種最短路徑算法，我們發現，最短路徑算法大概分為3步
- 初始化
- 松弛
- 判斷是否有負值環
其中Bellman-Ford（松弛以后如果還能松弛則有負值環）與SPFA（每個元素的入隊次數不能超過n）能檢測負值環。
我們簡單的說一下4種算法的松弛過程：
- Dijkstra：由源點出發，松弛每條邊。然后選出其中最小的邊，將其作為中間點，松弛其他未訪問的邊，如此循環n-1次。
- Bellman-Ford：遍歷所有邊，查看兩個端點能否通過這條邊進行松弛。
- SPFA：用隊列來優化Bellman-Ford，從隊列中取出某個點，查看經過這個點能否使邊松弛，如果能夠松弛并且沒有在隊列中，將另一個點加入隊列中。
- Floyd：遍歷所有的頂點，看看這個頂點是否能讓任意兩個頂點松弛。
</ol>
時間復雜度：
Dijkstra：普通：O(V^2+E)，最小堆優化：O(VlogV+ElogE)，斐波那契堆優化：O(E+VlogV)
Bellman-Ford：O(VE)
SPFA：O(kE)，有爭論，總之比Bellman-Ford更加快
Floyd：O(V^3)
Reference：
1. http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html
2. http://www.nocow.cn/index.php/Dijkstra%E7%AE%97%E6%B3%95
3. http://blog.csdn.net/collonn/article/details/18155655
4. http://blog.csdn.net/mengxiang000000/article/details/50266373