快捷導(dǎo)航

SPFA 算法實例講解

更新時間：2017年07月14日 08:51:54 投稿：jingxian

下面小編就為大家?guī)硪黄猄PFA 算法實例講解。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧

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

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

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

實現(xiàn)方法：

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

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

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

首先建立起始點a到其余各點的

最短路徑表格

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

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

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

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

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

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

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

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

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

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

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

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

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

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

隊首元素b點出隊，對以b為起始點的所有邊的終點依次進(jìn)行松弛操作（此處只有e這個點），此時路徑表格狀態(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個頂點到其它頂點之間的最短距離
 //數(shù)組實現(xiàn)鄰接表存儲
 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("存在負(fù)環(huán)");
  }
 }
 /*
  * 參數(shù)n:給定圖的頂點個數(shù)
  * 參數(shù)s:求取第s個頂點到其它所有頂點之間的最短距離
  * 參數(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個頂點到自身距離為0
  used[s]=true;//表示第s個頂點進(jìn)入數(shù)組隊
  num[s]=1;//表示第s個頂點已被遍歷一次
  list.add(s); //第s個頂點入隊
  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]的起點時
    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已進(jìn)入數(shù)組隊
     }
    }
   }
   used[a]=false; //頂點a出數(shù)組對
  }
  return true;
 }
}

以上這篇SPFA 算法實例講解就是小編分享給大家的全部內(nèi)容了，希望能給大家一個參考，也希望大家多多支持腳本之家。