シングルソース最短_spfa
10212 ワード
SPFA
適用範囲:与えられた図には負の重みエッジが存在し、Dijkstraのようなアルゴリズムは武力を使う場所がなく、Bellman-Fordアルゴリズムの複雑さが高すぎて、SPFAアルゴリズムが役に立ちました.重み付け図Gには負の重み回路が存在しないこと,すなわち最短経路は必ず存在することを約束する.所望の時間複雑度O(ke)は、kがすべての頂点のキューに入る平均回数であり、kが一般的に2以下であることを証明することができる.
負ループの有無の判断:あるポイントがキューに入る回数がN回を超えると負ループが存在する
アルゴリズム擬似コード:
P 3371【テンプレート】シングルソース最短パス題意:始点から各点までの最短パスを求める
Wormholes題意:図は連通しており、負のループ題解を判断する:任意の起点でspfaを行う
実は、spfaはDFSの形式に書くことができて、ただキューをスタックに変えただけです!同時に、bfs形式のspfaで負のループを判断するのは遅いです.負のループがある場合、ある点にn回エンキューしてから判断しなければなりません.nが大きいと、非常に時間がかかりますが、DFSで改善することができます.DFSは1つの点をスタックに繰り返すのではなく、次の点をスタックに入れるからです.
負のループを判断する方法を見てみましょう.1、現在のノードがスタック中にあるかどうかをspfaで同時に記録する .2、ノードが現在のノードによって緩和され得る場合 ノードはスタック内にあり、緩和経路にループが現れることを示し、 を終了する.そうでない場合、このノードを現在の点としてspfa検索動作 を行う.
しかし、図に負のループがないことを明確に知っていれば、最短経路を求めるだけなのか、BFSのspfaを使うのか、DFSスタックが深すぎて走るのが遅い!
ここではspfa_を先に示しますdfsは最短のコード(実はすでに負のループを判断することができます)を求めて工事の継続的な問題の意味をスムーズにします:起点の終点を与えて、最短のルートを求めます
Wormholes題意:図は連通しており、負のループ題解を判断する:任意の起点でspfaを行う
実は、負のループを判断するだけで、最短のパスを求める必要がなければ、dfsのspfaには最適化の場所があります!まず、負のループが存在する場合、あるエッジが負であることは間違いありません.最初から負のエッジからspfaを行うとします.dfsなら、すぐにこの負のリングを見つけることができ、負のリングを見つけると退出し、このように速くなります.
では、最初はどうやって負の辺を見つけますか??まずspfaを見てみましょうdfsでは、現在、1回目のdfs拡張が行う、1回目に負のエッジが選択されるようにするには、dis配列を0に初期化し、拡張を行うと、dis[u]=0、dis[v]=0となり、dis[v]>dis[u]+edge[i]となる.val,では辺は必ず負で,それから負の辺を拡張した.すなわち,dis配列は0に初期化される.このように処理すると,最初の拡張は起点に接続された辺権が負の辺にのみ広がる.もちろん,負ループ+最短ループを求める場合はdis配列をこのように初期化することはできないが,重みが負の経路が存在し負ループが存在しない可能性があるため,このような最短ループが合理的であるため,正直にdis配列を∞に初期化する.
P 3385【テンプレート】負ループ題意:図を与え、負ループがあるか否かを判断する.図は必ずしも連通しているとは限らないので、複数の異なる起点単源最短判定負ループを通過しなければならない.(spfa_bfsはタイムアウトし、spfa_dfsのdis配列は0に初期化しなくてもタイムアウトする)
また、グローバル変数flagを用いたdfsをもう一つあげましょう.実は上と同じです.
適用範囲:与えられた図には負の重みエッジが存在し、Dijkstraのようなアルゴリズムは武力を使う場所がなく、Bellman-Fordアルゴリズムの複雑さが高すぎて、SPFAアルゴリズムが役に立ちました.重み付け図Gには負の重み回路が存在しないこと,すなわち最短経路は必ず存在することを約束する.所望の時間複雑度O(ke)は、kがすべての頂点のキューに入る平均回数であり、kが一般的に2以下であることを証明することができる.
負ループの有無の判断:あるポイントがキューに入る回数がN回を超えると負ループが存在する
アルゴリズム擬似コード:
procedure Shortest-Path-Faster-Algorithm(G, s)
1 for each vertex v ≠ s in V(G)
2 d(v) := ∞
3 d(s) := 0
4 offer s into Q
5 while Q is not empty
6 u := poll Q
7 for each edge (u, v) in E(G)
8 if d(u) + w(u, v) < d(v) then
9 d(v) := d(u) + w(u, v)
10 if v is not in Q then
11 offer v into Q
P 3371【テンプレート】シングルソース最短パス題意:始点から各点までの最短パスを求める
#include
#include
#include
#include
using namespace std;
const int MAXN=10010;
const int MAXE=500010;
const int INF=0x7fffffff;
struct Node
{
int to,next,val;
};
Node edge[MAXE];
int cnt,head[MAXN];
int dis[MAXN],inque[MAXN];//
void addEdge(int u,int v,int val)
{
edge[cnt].to=v;edge[cnt].val=val;
edge[cnt].next=head[u];head[u]=cnt++;
}
void spfa_bfs(int st)
{
memset(inque,0,sizeof(inque));
dis[st]=0;
queue que;
que.push(st);
int u,v,i;
while(!que.empty())
{
u=que.front();que.pop();
inque[u]=0;
for(i=head[u];i!=-1;i=edge[i].next)
{
v=edge[i].to;
if(dis[v]>dis[u]+edge[i].val)
{
dis[v]=dis[u]+edge[i].val;
if(!inque[v])
{
que.push(v);
inque[v]=1;
}
}
}
}
}
int main()
{
int n,m,st,u,v,val;
scanf("%d%d%d",&n,&m,&st);
fill(dis+1,dis+1+n,INF);
memset(head,-1,sizeof(head));
cnt=0;
for(int i=0;i Wormholes題意:図は連通しており、負のループ題解を判断する:任意の起点でspfaを行う
#include
#include
#include
#include
using namespace std;
const int MAXN=10010;
const int MAXE=500010;
const int INF=0x3f3f3f3f;
struct Node
{
int to,next,val;
};
Node edge[MAXE];
int cnt,head[MAXN];
int dis[MAXN],inque[MAXN];
int queNum[MAXN];//
void addEdge(int u,int v,int val)
{
edge[cnt].to=v;edge[cnt].val=val;
edge[cnt].next=head[u];head[u]=cnt++;
}
bool spfa_bfs(int st,int n)
{
memset(inque,0,sizeof(inque));
memset(dis,INF,sizeof(dis));
memset(queNum,0,sizeof(queNum));
dis[st]=0;
queue que;
que.push(st);
queNum[st]++;
int u,v,i;
while(!que.empty())
{
u=que.front();que.pop();
inque[u]=0;
for(i=head[u];i!=-1;i=edge[i].next)
{
v=edge[i].to;
if(dis[v]>dis[u]+edge[i].val)
{
dis[v]=dis[u]+edge[i].val;
if(!inque[v])
{
que.push(v);
queNum[v]++;
if(queNum[v]>n) return true;//
inque[v]=1;
}
}
}
}
return false;
}
int main()
{
int n,m,k,u,v,val,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
memset(head,-1,sizeof(head));
cnt=0;
for(int i=0;i 実は、spfaはDFSの形式に書くことができて、ただキューをスタックに変えただけです!同時に、bfs形式のspfaで負のループを判断するのは遅いです.負のループがある場合、ある点にn回エンキューしてから判断しなければなりません.nが大きいと、非常に時間がかかりますが、DFSで改善することができます.DFSは1つの点をスタックに繰り返すのではなく、次の点をスタックに入れるからです.
負のループを判断する方法を見てみましょう.
しかし、図に負のループがないことを明確に知っていれば、最短経路を求めるだけなのか、BFSのspfaを使うのか、DFSスタックが深すぎて走るのが遅い!
ここではspfa_を先に示しますdfsは最短のコード(実はすでに負のループを判断することができます)を求めて工事の継続的な問題の意味をスムーズにします:起点の終点を与えて、最短のルートを求めます
#include
#include
#include
using namespace std;
const int MAXN=10010;
const int MAXE=500010;
const int INF=0x7fffffff;
struct Node
{
int to,next,val;
};
Node edge[MAXE];
int cnt,head[MAXN];
int dis[MAXN],instack[MAXN];//
void addEdge(int u,int v,int val)
{
edge[cnt].to=v;edge[cnt].val=val;
edge[cnt].next=head[u];head[u]=cnt++;
}
bool spfa_dfs(int u)
{
instack[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].val)
{
dis[v]=dis[u]+edge[i].val;
if(!instack[v])
{
if(spfa_dfs(v)) return true;//
}
else return true;//
}
}
instack[u]=0;
return false;
}
int main()
{
int n,m,st,ed,u,v,val;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(head,-1,sizeof(head));
cnt=0;
for(int i=0;i Wormholes題意:図は連通しており、負のループ題解を判断する:任意の起点でspfaを行う
#include
#include
#include
using namespace std;
const int MAXN=10010;
const int MAXE=500010;
const int INF=0x3f3f3f3f;
struct Node
{
int to,next,val;
};
Node edge[MAXE];
int cnt,head[MAXN];
int dis[MAXN],inStack[MAXN];//
void addEdge(int u,int v,int val)
{
edge[cnt].to=v;edge[cnt].val=val;
edge[cnt].next=head[u];head[u]=cnt++;
}
bool spfa_dfs(int u)
{
inStack[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].val)
{
dis[v]=dis[u]+edge[i].val;
if(!inStack[v])
{
if(spfa_dfs(v)) return true;//
}
else return true;//
}
}
inStack[u]=0;
return false;
}
int main()
{
int n,m,k,u,v,val,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
memset(head,-1,sizeof(head));
cnt=0;
for(int i=0;i 実は、負のループを判断するだけで、最短のパスを求める必要がなければ、dfsのspfaには最適化の場所があります!まず、負のループが存在する場合、あるエッジが負であることは間違いありません.最初から負のエッジからspfaを行うとします.dfsなら、すぐにこの負のリングを見つけることができ、負のリングを見つけると退出し、このように速くなります.
では、最初はどうやって負の辺を見つけますか??まずspfaを見てみましょうdfsでは、現在、1回目のdfs拡張が行う、1回目に負のエッジが選択されるようにするには、dis配列を0に初期化し、拡張を行うと、dis[u]=0、dis[v]=0となり、dis[v]>dis[u]+edge[i]となる.val,では辺は必ず負で,それから負の辺を拡張した.すなわち,dis配列は0に初期化される.このように処理すると,最初の拡張は起点に接続された辺権が負の辺にのみ広がる.もちろん,負ループ+最短ループを求める場合はdis配列をこのように初期化することはできないが,重みが負の経路が存在し負ループが存在しない可能性があるため,このような最短ループが合理的であるため,正直にdis配列を∞に初期化する.
P 3385【テンプレート】負ループ題意:図を与え、負ループがあるか否かを判断する.図は必ずしも連通しているとは限らないので、複数の異なる起点単源最短判定負ループを通過しなければならない.(spfa_bfsはタイムアウトし、spfa_dfsのdis配列は0に初期化しなくてもタイムアウトする)
#include
#include
#include
using namespace std;
const int MAXN=200010;
const int MAXE=200010*2;
const int INF=0x3f3f3f3f;
struct Node
{
int to,next,val;
};
Node edge[MAXE];
int cnt,head[MAXN];
int dis[MAXN],inStack[MAXN];//
void addEdge(int u,int v,int val)
{
edge[cnt].to=v;edge[cnt].val=val;
edge[cnt].next=head[u];head[u]=cnt++;
}
bool spfa_dfs(int u)
{
inStack[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].val)
{
dis[v]=dis[u]+edge[i].val;
if(!inStack[v])
{
if(spfa_dfs(v)) return true;//
}
else return true;//
}
}
inStack[u]=0;
return false;
}
int main()
{
int n,m,u,v,val,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
memset(head,-1,sizeof(head));
cnt=0;
for(int i=0;i=0) addEdge(v,u,val);
}
memset(inStack,0,sizeof(inStack));
memset(dis,0,sizeof(dis));
bool flag=false;
for(int i=1;i<=n;i++)
{
if(spfa_dfs(i))
{
flag=true;
break;
}
}
if(flag) printf("YE5
");
else printf("N0
");
}
}
また、グローバル変数flagを用いたdfsをもう一つあげましょう.実は上と同じです.
#include
#include
#include
using namespace std;
const int MAXN=200010;
const int MAXE=200010*2;
const int INF=0x3f3f3f3f;
struct Node
{
int to,next,val;
};
Node edge[MAXE];
int cnt,head[MAXN];
int dis[MAXN],inStack[MAXN];//
void addEdge(int u,int v,int val)
{
edge[cnt].to=v;edge[cnt].val=val;
edge[cnt].next=head[u];head[u]=cnt++;
}
bool flag;
void spfa_dfs(int u)
{
inStack[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].val)
{
dis[v]=dis[u]+edge[i].val;
if(!inStack[v])
{
spfa_dfs(v);
if(flag) return;//
}
else
{
flag=true;
return;//
}
}
}
inStack[u]=0;
}
int main()
{
int n,m,u,v,val,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
memset(head,-1,sizeof(head));
cnt=0;
for(int i=0;i=0) addEdge(v,u,val);
}
memset(inStack,0,sizeof(inStack));
memset(dis,0,sizeof(dis));
flag=false;
for(int i=1;i<=n;i++)
{
spfa_dfs(i);
if(flag) break;
}
if(flag) printf("YE5
");
else printf("N0
");
}
}