単一始点最短経路問題
単一始点最短経路問題
始点が固定されているとき、始点からその他の各頂点への最短距離を求める問題です。
幅優先探索
後述するダイクストラ法について、全ての辺の重みを1としても同じようなことができます。
時間計算量がO(VE)なので、ダイクストラよりちょっとだけ早い。
ベルマン・フォード法
重みが負の辺を含む場合や、負の閉路を検出するような問題に有効です。
負の辺が無くても問題なく機能しますが、その場合はダイクストラ法を使うほうがいいです(時間計算量的に)。
時間計算量はO(VE)です。
入力される辺が必ずしも都合のいい順に入力されるとは限らないため、V-1回のループ毎に全ての辺を見直すことで最短経路が求められます。
sからvへの最短経路をP(s,v)とする。P(s,v)=(s,A,B,C,v)であったとするときに、
s、A
A、B
B、C
C、v
の順で入力されるとは限らない。
負の閉路の検出
V-1回の更新が終わると各頂点の最短経路が求まっているはずですが、確定後に一回すべての辺を辿りなおすことで負の閉路の検出が可能です。
問題例 (引用元はこちら)
与えられたグラフ G=(V,E)と始点rについて、単一始点最短経路の重みを求めるプログラムを作成してください。
Gのノードrを始点とし、rから各ノードについて、最短経路上の辺の重みの総和を出力してください。
解答例
#include <bits/stdc++.h>
#define INF 1LL<<60
using namespace std;
struct Edge{
int from,to;
long long cost;
};
int main(){
int v,e,r;
cin>>v>>e>>r;
vector<Edge> edge(e);
for(int i=0;i<e;i++){
int s,t;
long long d;
cin>>s>>t>>d;
edge[i]={s,t,d};
}
vector<long long> ans(v,INF);
ans[r]=0;
for(int i=0;i<v-1;i++){
bool judge=false;
for(auto tmp:edge){
if(ans[tmp.from]!=INF && ans[tmp.to]>ans[tmp.from]+tmp.cost){
ans[tmp.to]=ans[tmp.from]+tmp.cost;
judge=true;
}
}
if(!judge) break;
}
for(auto tmp:edge){
if(ans[tmp.from]!=INF && ans[tmp.to]>ans[tmp.from]+tmp.cost){
cout<<"NEGATIVE CYCLE"<<endl;
return 0;
}
}
for(auto tmp:ans){
if(tmp==(1LL<<60)) cout<<"INF"<<endl;
else cout<<tmp<<endl;
}
}
ダイクストラ法
重みが負の辺を含まないグラフにおいて使用できます。
時間計算量はO((V+E)logV)です。
個人的には一番よく使う感覚があります。
無向グラフなのか、有向グラフなのかはしっかり確認しましょう。
例えば以下のような問題に使うことができます (引用元はこちら)
問題例
与えられたグラフ G=(V,E) と始点rについて、単一始点最短経路の重みを求めるプログラムを作成してください。
Gのノード rを始点とし、rから各ノードについて、最短経路上の辺の重みの総和を出力してください。
解答例
int main(){
int v,e,r;
cin>>v>>e>>r;
vector<int> ans(v,-1);
ans[r]=0;
vector<vector<pair<int,int>>> dest(v);
for(int i=0;i<e;i++){
int s,t,d;
cin>>s>>t>>d;
dest[s].push_back(make_pair(d,t));
}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push(make_pair(0,r));
while(!pq.empty()){
int omomi=pq.top().first;
int chouten=pq.top().second;
pq.pop();
for(pair<int,int> tmp:dest[chouten]){
if(ans[tmp.second]==-1 || ans[tmp.second]>tmp.first+omomi){
ans[tmp.second]=tmp.first+omomi;
pq.push(make_pair(ans[tmp.second],tmp.second));
}
}
}
for(auto tmp:ans){
if(tmp==-1) cout<<"INF"<<endl;
else cout<<tmp<<endl;
}
}