最短問題テンプレートであるディジェストラアルゴリズム(Dijstra)、Bellman-Fordアルゴリズム、フロイドアルゴリズム(Floyd-Warshall)、SPFAアルゴリズム
11262 ワード
Dijstraアルゴリズム:
Bellman-Fordアルゴリズム:
Bellman-Fordは負の重みループがあるかどうかを判断します.
Floyd-Warshallアルゴリズム:
SPFAアルゴリズム:
//POJ 2378
#include
using namespace std;
#define MAXN 1005
const int INF = (1 << 30);
int t,V,d[MAXN],costs[MAXN][MAXN];
bool used[MAXN];
void dijkstra(int s){
fill(used,used + V + 1,false);
fill(d,d + V + 1,INF);
d[s]=0;
while(true){
int v = -1;
for(int i=1;i<=V;i++){
if(!used[i]&&(v==-1||d[i]if(v==-1) break;
used[v]=true;
for(int i = 1;i <= V;i ++){
d[i]=min(d[i],d[v]+costs[v][i]);
}
}
}
int main(void)
{
int x,y,c;
scanf("%d%d",&t,&V);
fill(costs[0],costs[0] + MAXN * MAXN,INF);
for(int i = 0;i < t;i ++){
scanf("%d%d%d",&x,&y,&c);
costs[x][y] = costs[y][x] = min(costs[x][y],c);
}
dijkstra(1);
cout << d[V] << endl;
return 0;
}
//POJ 2378
#include
#include
#define MAX_V 1005
#define INF (1 << 28)
using namespace std;
struct edge{int to,cost;edge(int a,int b):to(a),cost(b){}};
typedef pair<int,int> P;
int V,E,d[MAX_V];
vector G[MAX_V];
struct cmp{
bool operator () (P p1,P p2){
return p1.first > p2.first;
}
};
void dijkstra(int s){
priority_queue vector
,cmp>que;
fill(d,d + V,INF);
d[s] = 0;
que.push(P(0,s));
while(!que.empty()){
P p = que.top();que.pop();
int v = p.second;
if(d[v] < p.first) continue;
for(int i = 0;i < G[v].size();i ++){
edge e = G[v][i];
if(d[e.to] > d[v] + e.cost){
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to],e.to));
}
}
}
}
int main(void)
{
cin >> E >> V;
for(int i = 0;i < E;i ++){
int f,t,c;
cin >> f >> t >> c;
f --,t --;
G[f].push_back(edge(t,c));
G[t].push_back(edge(f,c));
}
dijkstra(0);
cout << d[V - 1] << endl;
return 0;
}
Bellman-Fordアルゴリズム:
struct edge { int from,to,cost; };
edge es[MAX_E];
int V,E,d[MAX_V];
void bellman_ford(int s){
fill(d,d + MAX_V,INF);
d[s] = 0;
while(true){
bool update = false;
for(int i = 0;i < E;i ++){
edge e = es[i];
if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost){
d[e.to] = d[e.from] + e.cost;
update = true;
}
}
if(!update) break;
}
}
Bellman-Fordは負の重みループがあるかどうかを判断します.
bool find_negative_loop(){
fill(d,d + MAX_V,0);
for(int i = 0;i < V;i ++){
for(int j = 0;j < E;j ++){
edge e = es[i];
if(d[e.to] > d[e.from] + e.cost){
d[e.to] = d[e.from] + e.cost;
if(i == V - 1) return true;// for
}
}
}
return false;
}
Floyd-Warshallアルゴリズム:
long long d[MAX_V][MAX_V];
long long V;
void floyd(){
for(long long k = 0;k < V;k ++){
for(long long i = 0;i < V;i ++){
for(long long j = 0;j < V;j ++){
d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
}
}
}
}
SPFAアルゴリズム:
// From ACM Template of kuangbin
struct Edge{
int v,cost;
Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector E[MAXN];
void addedge(int u,int v,int w){
E[u].push_back(Edge(v,w));
}
bool vis[MAXN];//
int cnt[MAXN];//
int d[MAXN];
bool SPFA(int s,int n){
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)d[i]=INF;
vis[s]=true;
d[s]=0;
queue<int>que;
while(!que.empty())que.pop();
que.push(s);
memset(cnt,0,sizeof(cnt));
cnt[s]=1;
while(!que.empty()){
int u=que.front();
que.pop();
vis[u]=false;
for(int i=0;iint v=E[u][i].v;
if(d[v]>d[u]+E[u][i].cost){
d[v]=d[u]+E[u][i].cost;
if(!vis[v]){
vis[v]=true;
que.push(v);
if(++cnt[v]>n)return false;
}
}
}
}
return true;
}