作者：胡東麒
ID：國服墨子
學(xué)校：長沙市砂子塘小學(xué) 六年級(jí)
博客地址：https://www./blog/359614/
Step 1:基本的SPFA最短路
Step 1 - 1:什么是SPFA？前身：bellman-ford 同Dijkstra,是一種單源最短路徑算法，不同的是以邊為研究對(duì)象，時(shí)間復(fù)雜度為O(n*m),但是它能跑負(fù)邊權(quán)，每一輪將每一條邊跑一邊，能松弛就松弛，所以最多n-1輪，每輪m次，然后。。。就T了： for(int i=1;i<n;i++)
for(int j=head[i];j;j=e[j].nxt)
if(dis[i]+e[j].w<dis[e[j].to])
dis[e[j].to]=dis[i]+e[j].w; 但是，太太太太慢了，一言不合就TLE，QAQ 在完全圖的情況下，bellman-ford甚至速度跟Floyd速度差不多。。。 那么。。。 隆重登場：SPFA！?。?/p> 因?yàn)槊看嗡沙诤?，只有與n松馳后的點(diǎn)相關(guān)的邊才會(huì)變，所以利用先進(jìn)先出的隊(duì)列，這就是SPFA的優(yōu)化原理，雖然快了一丟丟，但是還是比Dijkstra慢，但是人家能跑負(fù)邊權(quán)嘛對(duì)吧hhh 長得賊像Dijkstra的，比bellman-ford長N倍的代碼隆重登場！?。?/p> #include<bits/stdc++.h>
#define N 10000005
using namespace std;
int n,m,s,tot,head[N];
struct edge{
int to,w,nxt;
}e[N];
void add(int u,int v,int w){
tot++;
e[tot].to=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
return;
}
bool vis[N];
int dis[N];
void SPFA(int s){
queue<int>q;
for(int i=1;i<=n;i++){
dis[i]=1e9;
}
dis[s]=0;
q.push(s);
vis[s]=1;
int cur;
while(!q.empty()){
cur=q.front();
q.pop();
vis[cur]=0;
for(int i=head[cur];i!=0;i=e[i].nxt){
int v=e[i].to;
if(dis[v]>dis[cur]+e[i].w){
dis[v]=dis[cur]+e[i].w;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
return;
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
}
SPFA(s);
for(int i=1;i<=n;i++){
cout<<dis[i]<<' ';
}
return 0;
} Step 1 - 2 :Dijkstra與SPFA的優(yōu)劣比較Dijkstra:效率高，實(shí)用性強(qiáng)，但不能跑負(fù)邊權(quán)
SPFA:時(shí)間復(fù)雜度為O(玄學(xué)),但能跑負(fù)權(quán)
Step 2:負(fù)環(huán)Step 2 - 1:碰到負(fù)環(huán)怎么辦？定義：在圖中有一個(gè)環(huán)，權(quán)值和為負(fù)數(shù)。 影響：如果有負(fù)環(huán)，最短路會(huì)無限變小，會(huì)死循環(huán)。 如圖： 
對(duì)于圖中的負(fù)環(huán)，每跑一趟，邊權(quán)和就會(huì)減去 9 ，所以不會(huì)停止。 判斷： 1.從點(diǎn)判斷，每個(gè)點(diǎn)最多被松弛n-1次，直接上cnt[XXX]即可； #include<bits/stdc++.h>
#define N 1000005
using namespace std;
int n,m,s,tot,head[N],cnt[N];
struct edge{
int to,w,nxt;
}e[N];
void add(int u,int v,int w){
tot++;
e[tot].to=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
return;
}
bool vis[N];
int dis[N];
bool SPFA(int s){
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
queue<int>q;
for(int i=1;i<=n;i++){
dis[i]=1e9;
}
dis[s]=0;
q.push(s);
vis[s]=1;
int cur;
while(!q.empty()){
cur=q.front();
q.pop();
vis[cur]=0;
for(int i=head[cur];i!=0;i=e[i].nxt){
int v=e[i].to;
if(dis[v]>dis[cur]+e[i].w){
dis[v]=dis[cur]+e[i].w;
if(!vis[v]){
vis[v]=1;
cnt[v]++;
if(cnt[v]==n)return false;
q.push(v);
}
}
}
}
return 1;
}
int t;
int main(){
cin>>t;
while(t--){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
if(w>=0){
add(u,v,w);add(v,u,w);
}else add(u,v,w);
}
if(SPFA(1)==1){cout<<'NO'<<'\n';}else{cout<<'Yes';cout<<'\n';}
}
return 0;
} 然后。。。 AC!!! 但是，這種方法僅適用于構(gòu)成環(huán)的點(diǎn)數(shù)較少時(shí)。 1.從邊的角度出發(fā)：對(duì)于有n個(gè)點(diǎn)的圖，任意最短路中，最多包含n-1條邊，統(tǒng)計(jì)s~i的邊數(shù)即可。 #include<bits/stdc++.h>
#define N 1000005
using namespace std;
int n,m,s,tot,head[N],cnt[N];
struct edge{
int to,w,nxt;
}e[N];
void add(int u,int v,int w){
tot++;
e[tot].to=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
return;
}
bool vis[N];
int dis[N];
bool SPFA(int s){
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
memset(dis,0x3f,sizeof(dis));
queue<int>q;
dis[s]=0;
q.push(s);
vis[s]=1;
int cur;
while(!q.empty()){
cur=q.front();
q.pop();
vis[cur]=0;
for(int i=head[cur];i!=0;i=e[i].nxt){
int v=e[i].to;
if(dis[v]>dis[cur]+e[i].w){
dis[v]=dis[cur]+e[i].w;
cnt[v]=cnt[cur]+1;
if(cnt[v]==n)return false;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
return 1;
}
int t;
int main(){
cin>>t;
while(t--){
tot=0;
memset(head,0,sizeof(head));
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
if(w>=0){
add(u,v,w);add(v,u,w);
}else add(u,v,w);
}
if(SPFA(1)==1){cout<<'NO'<<'\n';}else{ cout<<'YES';cout<<'\n';}
}
return 0;
} 也AC了，而且快400ms 所以視點(diǎn)和邊的數(shù)量決定方法。 （PS：參考例題（如上代碼）） Step 2 - 2 ：負(fù)環(huán)判斷的優(yōu)劣邊:適合處理負(fù)環(huán)內(nèi)點(diǎn)多的情況，越多越快樂。
點(diǎn):適合處理負(fù)環(huán)內(nèi)點(diǎn)少但總點(diǎn)數(shù)多的情況，越少越快樂。
好啦，到這里，我們的SPFA學(xué)習(xí)就告一段落
完結(jié)撒花?。?！碼字真累
|
