spfa

百度百科上spfa的思路為：動態(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)行松弛操作，直至隊列空為止。
俗人的解釋:用普通隊列存點，每次拋出的點如果更新了周圍鄰居的距離并且這個點不在隊列中，那么這個鄰居點被更新了的就加入隊列尾。一直到所有操作都不會改變鄰居的距離，當(dāng)隊列為空時，當(dāng)然，這可能要特殊處理有沒有成負(fù)環(huán)（一般不會）。
百科上兩個優(yōu)化策略：

• SPFA算法有兩個優(yōu)化策略SLF和LLL——SLF：Small Label First 策略，設(shè)要加入的節(jié)點是j，隊首元素為i，若dist(j)<dist(i)，則將j插入隊首，否則插入隊尾； LLL：Large Label Last 策略，設(shè)隊首元素為i，隊列中所有dist值的平均值為x，若dist(i)>x則將i插入到隊尾，查找下一元素，直到找到某一i使得dist(i)<=x，則將i出隊進(jìn)行松弛操作。SLF 和 LLF 在隨機(jī)數(shù)據(jù)上表現(xiàn)優(yōu)秀，但是在正權(quán)圖上最壞情況為 O(VE)，在負(fù)權(quán)圖上最壞情況為達(dá)到指數(shù)級復(fù)雜度。

藍(lán)橋杯 最短路

這題用dijkstra過不了，只能用spfa.裸的spfa。
算法訓(xùn)練 最短路
時間限制：1.0s 內(nèi)存限制：256.0MB

問題描述
給定一個n個頂點，m條邊的有向圖（其中某些邊權(quán)可能為負(fù)，但保證沒有負(fù)環(huán)）。請你計算從1號點到其他點的最短路（頂點從1到n編號）。

輸入格式
第一行兩個整數(shù)n, m。

接下來的m行，每行有三個整數(shù)u, v, l，表示u到v有一條長度為l的邊。

輸出格式
共n-1行，第i行表示1號點到i 1號點的最短路。
樣例輸入
3 3
1 2 -1
2 3 -1
3 1 2
樣例輸出
-1
-2
數(shù)據(jù)規(guī)模與約定
對于10%的數(shù)據(jù)，n = 2，m = 2。

對于30%的數(shù)據(jù)，n <= 5，m <= 10。

對于100%的數(shù)據(jù)，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保證從任意頂點都能到達(dá)其他所有頂點。
JAVA代碼：

package 算法訓(xùn)練; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.List; import java.util.Queue; /** spfa算法*/ public class 最短路 {static int leng[];public static void main(String[] args) throws IOException {// TODO 自動生成的方法存根StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();int n=(int)in.nval;in.nextToken();int m=(int)in.nval;List<node>list[]=new ArrayList[n];//存儲路徑for(int i=0;i<n;i++)//聲明{list[i]=new ArrayList<>();}leng=new int[n];boolean jud[]=new boolean[n];//判斷是否在隊列內(nèi)for(int i=1;i<n;i++) {leng[i]=Integer.MAX_VALUE;}//初始最長均為maxfor(int i=0;i<m;i++){in.nextToken();int u=(int)in.nval;in.nextToken();int v=(int)in.nval;in.nextToken();int l=(int)in.nval;list[u-1].add(new node(v-1, l)); }Queue<Integer>q1=new ArrayDeque<Integer>();q1.add(0);//第一個while(!q1.isEmpty()){int x=q1.poll();jud[x]=false;for(int i=0;i<list[x].size();i++)//遍歷{int index=list[x].get(i).x;//x鄰居該節(jié)點的編號int length=list[x].get(i).leng;//x到這個鄰居的距離if(leng[index]>leng[x]+length){leng[index]=leng[x]+length;if(!jud[index])//隊列中沒有該點{q1.add(index);jud[index]=true;} } }}for(int i=1;i<n;i++){out.println(leng[i]);}out.flush();}static class node{int x;int leng;public node(int x,int leng){this.x=x;this.leng=leng;}} }

• 運行結(jié)果為

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯最短路(java过)spfa单源最短路算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。