題目大意：求圖上單點到單點之間的最短路。
題目分析：SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一種隊列實現(xiàn)，減少了不必要的冗余計算。
算法大致流程是用一個隊列來進行維護。 初始時將源加入隊列。 每次從隊列中取出一個元素，并對所有與他相鄰的點進行松弛，若某個相鄰的點松弛成功，則將其入隊。 直到隊列為空時算法結(jié)束。
這個算法，簡單的說就是隊列優(yōu)化的bellman-ford,利用了每個點不會更新次數(shù)太多的特點發(fā)明的此算法
SPFA——Shortest Path Faster Algorithm，它可以在O(kE)的時間復(fù)雜度內(nèi)求出源點到其他所有點的最短路徑，可以處理負(fù)邊。SPFA的實現(xiàn)甚至比Dijkstra或者Bellman_Ford還要簡單：
設(shè)Dist代表S到I點的當(dāng)前最短距離，F(xiàn)a代表S到I的當(dāng)前最短路徑中I點之前的一個點的編號。開始時Dist全部為+∞，只有Dist[S]=0，F(xiàn)a全部為0。
維護一個隊列，里面存放所有需要進行迭代的點。初始時隊列中只有一個點S。用一個布爾數(shù)組記錄每個點是否處在隊列中。
每次迭代，取出隊頭的點v，依次枚舉從v出發(fā)的邊v->u，設(shè)邊的長度為len，判斷Dist[v]+len是否小于Dist[u]，若小于則改進Dist[u]，將Fa[u]記為v，并且由于S到u的最短距離變小了，有可能u可以改進其它的點，所以若u不在隊列中，就將它放入隊尾。這樣一直迭代下去直到隊列變空，也就是S到所有的最短距離都確定下來，結(jié)束算法。若一個點入隊次數(shù)超過n，則有負(fù)權(quán)環(huán)。
SPFA 在形式上和寬度優(yōu)先搜索非常類似，不同的是寬度優(yōu)先搜索中一個點出了隊列就不可能重新進入隊列，但是SPFA中一個點可能在出隊列之后再次被放入隊列，也就是一個點改進過其它的點之后，過了一段時間可能本身被改進，于是再次用來改進其它的點，這樣反復(fù)迭代下去。設(shè)一個點用來作為迭代點對其它點進行改進的平均次數(shù)為k，有辦法證明對于通常的情況，k在2左右。
SPFA算法（Shortest Path Faster Algorithm），也是求解單源最短路徑問題的一種算法，用來解決：給定一個加權(quán)有向圖G和源點s，對于圖G中的任意一點v，求從s到v的最短路徑。 SPFA算法是Bellman-Ford算法的一種隊列實現(xiàn)，減少了不必要的冗余計算，他的基本算法和Bellman-Ford一樣，并且用如下的方法改進： 1、第二步，不是枚舉所有節(jié)點，而是通過隊列來進行優(yōu)化 設(shè)立一個先進先出的隊列用來保存待優(yōu)化的結(jié)點，優(yōu)化時每次取出隊首結(jié)點u，并且用u點當(dāng)前的最短路徑估計值對離開u點所指向的結(jié)點v進行松弛操作，如果v點的最短路徑估計值有所調(diào)整，且v點不在當(dāng)前的隊列中，就將v點放入隊尾。這樣不斷從隊列中取出結(jié)點來進行松弛操作，直至隊列空為止。 2、同時除了通過判斷隊列是否為空來結(jié)束循環(huán)，還可以通過下面的方法： 判斷有無負(fù)環(huán)：如果某個點進入隊列的次數(shù)超過V次則存在負(fù)環(huán)（SPFA無法處理帶負(fù)環(huán)的圖）。
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出對進行松弛操作。 SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高約 50%。 在實際的應(yīng)用中SPFA的算法時間效率不是很穩(wěn)定，為了避免最壞情況的出現(xiàn)，通常使用效率更加穩(wěn)定的Dijkstra算法。
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF (1<<29)
const int maxn = 1010;
typedef pair<
int,
int> P;
vector<P> G[maxn];
queue<
int> que;
int V, E, dist[maxn];
bool vis[maxn];
void spfa(
int s) {
fill(dist, dist+V, INF);
fill(vis, vis+V,
false);
dist[s] = 0;
while(!que.empty()) que.pop();
que.push(s);
while(!que.empty()) {
int u = que.front();
que.pop();
vis[u] =
false;
int sz = G[u].size();
for(
int i=0;i<sz;i++) {
int v = G[u][i].first;
int w = G[u][i].second;
if(dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
if(!vis[v]) {
vis[v] =
true;
que.push(v);
}
}
}
}
}
int main() {
scanf("%d%d" , &E, &V);
for(
int i=0;i<V;i++) G[i].clear();
for(
int i=0;i<E;i++) {
int u, v, w;
scanf("%d%d%d" , &u, &v, &w);
u --; v --;
G[u].push_back(make_pair(v, w));
G[v].push_back(make_pair(u, w));
}
spfa(0);
printf("%d\n", dist[V-1]);
return 0;
}
posted on 2015-02-13 19:42
JulyRina 閱讀(262)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告