什么情況下需要使用SPFA 算法

什么情況下需要使用SPFA 算法？相信很多沒有經(jīng)驗(yàn)的人對此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個問題。

適用范圍：給定的圖存在負(fù)權(quán)邊，這時類似Dijkstra等算法便沒有了用武之地，而Bellman-Ford算法的復(fù)雜度又過高，SPFA算法便 派上用場了。 我們約定有向加權(quán)圖G不存在負(fù)權(quán)回路，即最短路徑一定存在。當(dāng)然，我們可以在執(zhí)行該算法前做一次拓?fù)渑判颍耘袛嗍欠翊嬖谪?fù)權(quán)回路，但這不是我們討論的重 點(diǎn)。

算法思想：我們用數(shù)組d記錄每個結(jié)點(diǎn)的最短路徑估計值，用鄰接表來存儲圖G。我們采取的方法是動態(tài)逼近法：設(shè)立一個先進(jìn)先出的隊列用來保存待優(yōu)化的 結(jié)點(diǎn)，優(yōu)化時每次取出隊首結(jié)點(diǎn)u，并且用u點(diǎn)當(dāng)前的最短路徑估計值對離開u點(diǎn)所指向的結(jié)點(diǎn)v進(jìn)行松弛操作，如果v點(diǎn)的最短路徑估計值有所調(diào)整，且v點(diǎn)不在 當(dāng)前的隊列中，就將v點(diǎn)放入隊尾。這樣不斷從隊列中取出結(jié)點(diǎn)來進(jìn)行松弛操作，直至隊列空為止

期望的時間復(fù)雜度O(ke)， 其中k為所有頂點(diǎn)進(jìn)隊的平均次數(shù)，可以證明k一般小于等于2。

實(shí)現(xiàn)方法：

建立一個隊列，初始時隊列里只有起始點(diǎn)，再建立一個表格記錄起始點(diǎn)到所有點(diǎn)的最短路徑（該表格的初始值要賦為極大值，該點(diǎn)到他本身的路徑賦為 0）。然后執(zhí)行松弛操作，用隊列里有的點(diǎn)作為起始點(diǎn)去刷新到所有點(diǎn)的最短路，如果刷新成功且被刷新點(diǎn)不在隊列中則把該點(diǎn)加入到隊列最后。重復(fù)執(zhí)行直到隊列 為空。

判斷有無負(fù)環(huán)：

如果某個點(diǎn)進(jìn)入隊列的次數(shù)超過N次則存在負(fù)環(huán)（SPFA無法處理帶負(fù)環(huán)的圖）

首先建立起始點(diǎn)a到其余各點(diǎn)的

最短路徑表格

首先源點(diǎn)a入隊，當(dāng)隊列非空時：

１、隊首元素（a）出隊，對以a為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處有b,c,d三個點(diǎn)），此時路徑表格狀態(tài)為：

在松弛時三個點(diǎn)的最短路徑估值變小了，而這些點(diǎn)隊列中都沒有出現(xiàn)，這些點(diǎn)
需要入隊，此時，隊列中新入隊了三個結(jié)點(diǎn)b,c,d

隊首元素b點(diǎn)出隊，對以b為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處只有e點(diǎn)），此時路徑表格狀態(tài)為：

在最短路徑表中，e的最短路徑估值也變小了，e在隊列中不存在，因此e也要
入隊，此時隊列中的元素為c，d，e

隊首元素c點(diǎn)出隊，對以c為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處有e,f兩個點(diǎn)），此時路徑表格狀態(tài)為：

在最短路徑表中，e，f的最短路徑估值變小了，e在隊列中存在，f不存在。因此
e不用入隊了，f要入隊，此時隊列中的元素為d，e，f

隊首元素d點(diǎn)出隊，對以d為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處只有g(shù)這個點(diǎn)），此時路徑表格狀態(tài)為：

在最短路徑表中，g的最短路徑估值沒有變?。ㄋ沙诓怀晒Γ?，沒有新結(jié)點(diǎn)入隊，隊列中元素為f，g

隊首元素f點(diǎn)出隊，對以f為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處有d，e，g三個點(diǎn)），此時路徑表格狀態(tài)為：

在最短路徑表中，e，g的最短路徑估值又變小，隊列中無e點(diǎn)，e入隊，隊列中存在g這個點(diǎn)，g不用入隊，此時隊列中元素為g，e

隊首元素g點(diǎn)出隊，對以g為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處只有b點(diǎn)），此時路徑表格狀態(tài)為：

在最短路徑表中，b的最短路徑估值又變小，隊列中無b點(diǎn)，b入隊，此時隊列中元素為e，b
隊首元素e點(diǎn)出隊，對以e為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處只有g(shù)這個點(diǎn)），此時路徑表格狀態(tài)為：

在最短路徑表中，g的最短路徑估值沒變化（松弛不成功），此時隊列中元素為b

隊首元素b點(diǎn)出隊，對以b為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處只有e這個點(diǎn)），此時路徑表格狀態(tài)為：

在最短路徑表中，e的最短路徑估值沒變化（松弛不成功），此時隊列為空了

最終a到g的最短路徑為１４

java代碼

package spfa負(fù)權(quán)路徑;
 
import java.awt.List;
import java.util.ArrayList;
import java.util.Scanner;
public class SPFA {
 /**
  * @param args
  */
 public long[] result;   //用于得到第s個頂點(diǎn)到其它頂點(diǎn)之間的最短距離
 //數(shù)組實(shí)現(xiàn)鄰接表存儲
 class edge{
  public int a;//邊的起點(diǎn)
  public int b;//邊的終點(diǎn)
  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("存在負(fù)環(huán)");
  }
 }
 /*
  * 參數(shù)n:給定圖的頂點(diǎn)個數(shù)
  * 參數(shù)s:求取第s個頂點(diǎn)到其它所有頂點(diǎn)之間的最短距離
  * 參數(shù)edge:給定圖的具體邊
  * 函數(shù)功能：如果給定圖不含負(fù)權(quán)回路，則可以得到最終結(jié)果，如果含有負(fù)權(quán)回路，則不能得到最終結(jié)果
  */
 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個頂點(diǎn)到自身距離為0
  used[s]=true;//表示第s個頂點(diǎn)進(jìn)入數(shù)組隊
  num[s]=1;//表示第s個頂點(diǎn)已被遍歷一次
  list.add(s); //第s個頂點(diǎn)入隊
  while(list.size()!=0){
   int a=list.get(0);//獲取數(shù)組隊中第一個元素
   list.remove(0);//刪除數(shù)組隊中第一個元素
   for(int i=0;i<A.length;i++){
   //當(dāng)list數(shù)組隊的第一個元素等于邊A[i]的起點(diǎn)時
    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]的終點(diǎn)b已進(jìn)入數(shù)組隊
     }
    }
   }
   used[a]=false; //頂點(diǎn)a出數(shù)組對
  }
  return true;
 }
}

看完上述內(nèi)容，你們掌握什么情況下需要使用SPFA 算法的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！