一.理論準備
為了學習網絡流，先水一道spfa。
SPFA算法是1994年西南交通大學段凡丁提出，隻要最短路徑存在，SPFA算法必定能求出最小值，SPFA對Bellman-Ford算法優化的關鍵之處在于意識到：隻有那些在前一遍松弛中改變了距離估計值的點，才可能引起他們的鄰接點的距離估計值的改變。為什麼隊列為空就不改變了呢？就是因為要到下一點必須經過它的前一個鄰接點。。SPFA可以處理負權邊。很多時候，給定的圖存在負權邊，這時類似Dijkstra等算法便沒有了用武之地，而Bellman-Ford算法的複雜度又過高，SPFA算法便派上用場了。簡潔起見，我們約定有向權重圖G不存在負權回路，即最短路徑一定存在。當然，我們可以在執行該算法前做一次拓撲排序，以判斷是否存在負權回路。
初始化： dis數組全部指派為Inf(無窮大，不能是map[s][i]),path數組全部指派為s（即源點），或者指派為-1，表示還沒有知道前驅,然後dis[s]=0; 表示源點不用求最短路徑，或者說最短路就是0。将源點入隊；另外記住在整個算法中有頂點入隊了要記得标記vis數組，有頂點出隊了記得消除那個标記(可能多次入隊)。
核心：讀取隊頭頂點u，并将隊頭頂點u出隊（記得消除标記）；将與點u相連的所有點v進行松弛操作，如果能更新估計值（即令d[v]變小），那麼就更新，另外，如果點v沒有在隊列中，那麼要将點v入隊（記得标記），如果已經在隊列中了，那麼就不用入隊以此循環，直到隊空為止就完成了單源最短路的求解。
判斷有無負環：如果某個點進入隊列的次數超過N次則存在負環(SPFA無法處理帶負環的圖)，假設這個節點的入度是k(無向權則就是這個節點的連接配接的邊)如果進入這個隊列超過k,說明必然有某個邊重複了，即成環；換一種思路：用DFS，假設存在負環a1->a2->…->an->a1。那麼當從a1深搜下去時又遇到了a1，那麼直接可以判斷負環了所有用。當某個節點n次進入隊列，則存在負環，此時時間複雜度為O(n*m),n為節點，m為邊。
SPFA算法有兩個優化算法 SLF 和 LLL： SLF：Small Label First 政策，設要加入的節點是j，隊首元素為i，若dist(j)<dist(i)，則将j插入隊首，否則插入隊尾。 LLL：Large Label Last 政策，設隊首元素為i，隊列中所有dist值的平均值為x，若dist(i)>x則将i插入到隊尾，查找下一進制素，直到找到某一i使得dist(i)<=x，則将i出對進行松弛操作。 SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高約 50%。 在實際的應用中SPFA的算法時間效率不是很穩定，為了避免最壞情況的出現，通常使用效率更加穩定的Dijkstra算法。個人覺得LLL優化每次要求平均值，不太好，為了簡單，我們可以之間用c++STL裡面的優先隊列來進行SLF優化。
二.算法實作
直接去把HDU1874AC了吧。
1: import java.util.Comparator; 2: import java.util.PriorityQueue; 3: import java.util.Queue; 4: import java.util.Scanner; 5: /* 6: * 原來一直wa，重寫了一遍，AC了 7: * SLF優化 8: */ 9: public class HD1874 { 10: 11: static int n,m; 12: static int[][] map = new int[205][205]; 13: static int[] dis = new int[205]; 14: static boolean[] vis = new boolean[205]; 15: /* 16: * 路徑最大值是10000，不能設定成10005就行，還要考慮和 17: * 也不能是整形最大值，否則一加就溢出了 18: */ 19: static final int Inf = 0x3f3f3f3f; 20: 21: public static void main(String[] args) { 22: Scanner sc = new Scanner(System.in); 23: // 記錄前驅點 。若path[i]=j,表示從s到i的最短路徑中i的前一個點是j 24: //int[] path; 25: int u,v,w; 26: while(sc.hasNext()) { 27: n = sc.nextInt(); 28: m = sc.nextInt(); 29: for(int i=0; i<205; i++) { 30: for(int j=i; j<205; j++) { 31: map[i][j] = Inf; 32: map[j][i] = Inf; 33: } 34: } 35: for(int i=0; i<m; i++) { 36: u = sc.nextInt(); 37: v = sc.nextInt(); 38: w = sc.nextInt(); 39: //多重邊 40: if(map[u][v]>w) { 41: map[v][u] = w; 42: map[u][v] = w; 43: } 44: } 45: int s = sc.nextInt(); 46: int t = sc.nextInt(); 47: spfa(s); 48: //題目上有st<n，是以不必判斷dis[t]是否越界 49: //起點終點相同的話答案是0 50: if(Inf==dis[t]) { 51: System.out.println(-1); 52: }else { 53: System.out.println(dis[t]); 54: } 55: } 56: } 57: 58: private static void spfa(int s) { 59: 60: for(int i=0; i<205; i++) { 61: vis[i] = false; 62: //初始化為map[s][i]第一組資料就錯了 63: dis[i] = Inf; 64: } 65: dis[s] = 0; 66: vis[s] = true; 67: Comparator<Integer> cmp = new Comparator<Integer>() { 68: 69: public int compare(Integer o1, Integer o2) { 70: int i = (int)o1; 71: int j = (int)02; 72: if(dis[i]>dis[j]) { 73: return 1; 74: }else if(dis[i]==dis[j]){ 75: return 0; 76: }else { 77: return -1; 78: } 79: } 80: }; 81: //面向接口程式設計；205代表優先隊列(是類)的容量 82: Queue<Integer> q = new PriorityQueue<Integer>(205, cmp); 83: q.clear(); 84: q.offer(s); 85: while(!q.isEmpty()) { 86: int head = q.poll(); 87: //該注意的是有些點可能重複入隊，是以出隊的點也要重新置未标記 88: vis[head] = false; 89: for(int i=0; i<n; i++) { 90: //dis[head]不可能是INF，map[head][i]可能是INF 91: int temp = dis[head] + map[head][i]; 92: if(temp<dis[i]) { 93: //path[i] = head 94: dis[i] = temp; 95: if(!vis[i]) { 96: //用一個數組在此記錄入隊次數，大于n就存在負環；如何事先判斷 97: q.offer(i); 98: vis[i] = true; 99: } 100: } 101: } 102: } 103: } 104: 105: } 106:
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)