快捷導(dǎo)航

SPFA 算法實(shí)例講解

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

下面小編就為大家?guī)?lái)一篇SPFA 算法實(shí)例講解。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來(lái)看看吧

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

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

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

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

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

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

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

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

最短路徑表格

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

最終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個(gè)頂點(diǎn)到其它頂點(diǎn)之間的最短距離
 //數(shù)組實(shí)現(xiàn)鄰接表存儲(chǔ)
 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)個(gè)數(shù)
  * 參數(shù)s:求取第s個(gè)頂點(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個(gè)頂點(diǎn)到自身距離為0
  used[s]=true;//表示第s個(gè)頂點(diǎn)進(jìn)入數(shù)組隊(duì)
  num[s]=1;//表示第s個(gè)頂點(diǎn)已被遍歷一次
  list.add(s); //第s個(gè)頂點(diǎn)入隊(duì)
  while(list.size()!=0){
   int a=list.get(0);//獲取數(shù)組隊(duì)中第一個(gè)元素
   list.remove(0);//刪除數(shù)組隊(duì)中第一個(gè)元素
   for(int i=0;i<A.length;i++){
   //當(dāng)list數(shù)組隊(duì)的第一個(gè)元素等于邊A[i]的起點(diǎn)時(shí)
    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ù)組隊(duì)
     }
    }
   }
   used[a]=false; //頂點(diǎn)a出數(shù)組對(duì)
  }
  return true;
 }
}

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