適用范圍：給定的圖存在負權邊，這時類似dijkstra等算法便沒有了用武之地，而bellman-ford算法的復雜度又過高，spfa算法便 派上用場了。 我們約定有向加權圖g不存在負權回路，即最短路徑一定存在。當然，我們可以在執行該算法前做一次拓撲排序，以判斷是否存在負權回路，但這不是我們討論的重 點。
算法思想：我們用數組d記錄每個結點的最短路徑估計值，用鄰接表來存儲圖g。我們采取的方法是動態逼近法：設立一個先進先出的隊列用來保存待優化的 結點，優化時每次取出隊首結點u，并且用u點當前的最短路徑估計值對離開u點所指向的結點v進行松弛操作，如果v點的最短路徑估計值有所調整，且v點不在 當前的隊列中，就將v點放入隊尾。這樣不斷從隊列中取出結點來進行松弛操作，直至隊列空為止
期望的時間復雜度o(ke)， 其中k為所有頂點進隊的平均次數，可以證明k一般小于等于2。
實現方法：
建立一個隊列，初始時隊列里只有起始點，再建立一個表格記錄起始點到所有點的最短路徑（該表格的初始值要賦為極大值，該點到他本身的路徑賦為 0）。然后執行松弛操作，用隊列里有的點作為起始點去刷新到所有點的最短路，如果刷新成功且被刷新點不在隊列中則把該點加入到隊列最后。重復執行直到隊列 為空。
判斷有無負環：
如果某個點進入隊列的次數超過n次則存在負環（spfa無法處理帶負環的圖）
首先建立起始點a到其余各點的
最短路徑表格
首先源點a入隊，當隊列非空時：
１、隊首元素（a）出隊，對以a為起始點的所有邊的終點依次進行松弛操作（此處有b,c,d三個點），此時路徑表格狀態為：
在松弛時三個點的最短路徑估值變小了，而這些點隊列中都沒有出現，這些點
需要入隊，此時，隊列中新入隊了三個結點b,c,d
隊首元素b點出隊，對以b為起始點的所有邊的終點依次進行松弛操作（此處只有e點），此時路徑表格狀態為：
在最短路徑表中，e的最短路徑估值也變小了，e在隊列中不存在，因此e也要
入隊，此時隊列中的元素為c，d，e
隊首元素c點出隊，對以c為起始點的所有邊的終點依次進行松弛操作（此處有e,f兩個點），此時路徑表格狀態為：
在最短路徑表中，e，f的最短路徑估值變小了，e在隊列中存在，f不存在。因此
e不用入隊了，f要入隊，此時隊列中的元素為d，e，f
隊首元素d點出隊，對以d為起始點的所有邊的終點依次進行松弛操作（此處只有g這個點），此時路徑表格狀態為：
在最短路徑表中，g的最短路徑估值沒有變小（松弛不成功），沒有新結點入隊，隊列中元素為f，g
隊首元素f點出隊，對以f為起始點的所有邊的終點依次進行松弛操作（此處有d，e，g三個點），此時路徑表格狀態為：
在最短路徑表中，e，g的最短路徑估值又變小，隊列中無e點，e入隊，隊列中存在g這個點，g不用入隊，此時隊列中元素為g，e
隊首元素g點出隊，對以g為起始點的所有邊的終點依次進行松弛操作（此處只有b點），此時路徑表格狀態為：
在最短路徑表中，b的最短路徑估值又變小，隊列中無b點，b入隊，此時隊列中元素為e，b
隊首元素e點出隊，對以e為起始點的所有邊的終點依次進行松弛操作（此處只有g這個點），此時路徑表格狀態為：
在最短路徑表中，g的最短路徑估值沒變化（松弛不成功），此時隊列中元素為b
隊首元素b點出隊，對以b為起始點的所有邊的終點依次進行松弛操作（此處只有e這個點），此時路徑表格狀態為：
在最短路徑表中，e的最短路徑估值沒變化（松弛不成功），此時隊列為空了
最終a到g的最短路徑為１４
java代碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
package spfa負權路徑; import java.awt.list;import java.util.arraylist;import java.util.scanner;public class spfa { /** * @param args */ public long[] result; //用于得到第s個頂點到其它頂點之間的最短距離 //數組實現鄰接表存儲 class edge{ public int a;//邊的起點 public int b;//邊的終點 public int value;//邊的值 public edge(int a,int b,int value){ this.a=a; this.b=b; this.value=value; } } public static void main(string[] args) { // todo auto-generated method stub spfa spafa=new spfa(); scanner scan=new scanner(system.in); int n=scan.nextint(); int s=scan.nextint(); int p=scan.nextint(); edge[] a=new edge[p]; for(int i=0;i<p;i++){ int a=scan.nextint(); int b=scan.nextint(); int value=scan.nextint(); a[i]=spafa.new edge(a,b,value); } if(spafa.getshortestpaths(n,s,a)){ for(int i=0;i<spafa.result.length;i++){ system.out.println(spafa.result[i]+" "); } }else{ system.out.println("存在負環"); } } /* * 參數n:給定圖的頂點個數 * 參數s:求取第s個頂點到其它所有頂點之間的最短距離 * 參數edge:給定圖的具體邊 * 函數功能：如果給定圖不含負權回路，則可以得到最終結果，如果含有負權回路，則不能得到最終結果 */ private boolean getshortestpaths(int n, int s, edge[] a) { // todo auto-generated method stub arraylist<integer> list = new arraylist<integer>(); result=new long[n]; boolean used[]=new boolean[n]; int num[]=new int[n]; for(int i=0;i<n;i++){ result[i]=integer.max_value; used[i]=false; } result[s]=0;//第s個頂點到自身距離為0 used[s]=true;//表示第s個頂點進入數組隊 num[s]=1;//表示第s個頂點已被遍歷一次 list.add(s); //第s個頂點入隊 while(list.size()!=0){ int a=list.get(0);//獲取數組隊中第一個元素 list.remove(0);//刪除數組隊中第一個元素 for(int i=0;i<a.length;i++){ //當list數組隊的第一個元素等于邊a[i]的起點時 if(a==a[i].a&&result[a[i].b]>(result[a[i].a]+a[i].value)){ result[a[i].b]=result[a[i].a]+a[i].value; if(!used[a[i].b]){ list.add(a[i].b); num[a[i].b]++; if(num[a[i].b]>n){ return false; } used[a[i].b]=true;//表示邊a[i]的終點b已進入數組隊 } } } used[a]=false; //頂點a出數組對 } return true; }} |
以上這篇spfa 算法實例講解就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持服務器之家。
