注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

最短路四种算法汇总(hdu 2544)  

2012-08-06 17:30:06|  分类: ACM-Steps |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
最短路是个经典的问题,常见的有四种算法:
Dijkstra,Bellman-Ford,Floyed,SPFA
总结一下这四种算法,就拿hdu 2544这一题来说,下面列了以上四种算法的代码(hdu 2544是个最短路的经典题):

Dijkstra

#include<iostream>
using namespace std;
const int maxnum = 110;
const int maxint = 999999;
int dist[maxnum];
int c[maxnum][maxnum];
int n, line;

void Dijkstra(int v)
{
int i,j,tmp,u;
bool s[maxnum];
for(i=1; i<=n; ++i)
{
dist[i] = c[v][i];
s[i] = 0;
}
dist[v] = 0;
s[v] = 1;
for(i=1; i<=n; ++i)
{
tmp = maxint;
u = v;
for(j=1; j<=n; ++j)
if((!s[j]) && dist[j]<tmp)
{
u = j;
tmp = dist[j];
}
if(tmp==maxint)
return ;
s[u] = 1;
for(j=1; j<=n; ++j)
if((!s[j]) && dist[u] + c[u][j] < dist[j])
dist[j]=dist[u] + c[u][j];
}
}

int main()
{
int p, q, len,i,j;
while(scanf("%d%d",&n,&line))
{
if(n==0 && line==0)
break;
for(i=1; i<=n; ++i)
for(j=1; j<=n; ++j)
c[i][j] = maxint;
while(line--)
{
scanf("%d%d%d",&p,&q,&len);
if(len < c[p][q])
{
c[p][q] = len;
c[q][p] = len;
}
}
for(i=1; i<=n; ++i)
dist[i] = maxint;
Dijkstra(1);
printf("%d\n",dist[n]);
}
return 0;
}


Bellman-Ford

/*
* fudq.cpp
*
* Created on: 2012-08-06
* Author: fudq
* hdu: 最短路(Bellman_Ford)
*/
#include<algorithm>
#include<stdio.h>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<stack>
#include<map>
#include<iostream>
using namespace std;

const int N = 205;
const int M = 20005;
const int MAX = 1000000000;

int dis[N];
struct edge
{
int u;
int v;
int w;
}e[M];

void init(int vs, int s)
{
for (int i=1; i<=vs; ++i)
dis[i] = MAX;
dis[s] = 0;
return ;
}

bool relax(int u, int v, int w)
{
if (dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
return true;
}
return false;
}

void bellmanFord(int es, int vs, int s)
{
//es表示边数,vs表示点数,s表示起点
init(vs, s);
int flag;
for (int i=1; i<vs; ++i)
{
flag=false;
for (int j=0; j<es; ++j)
if(relax(e[j].u, e[j].v, e[j].w))
flag=true;
if(!flag)
return ;
}
}

int main()
{
int n, m;
while (scanf("%d%d", &n, &m), n+m)
{
for (int i=0; i<m; ++i)
{
scanf ("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
e[m+i].u = e[i].v;
e[m+i].v = e[i].u;
e[m+i].w = e[i].w;
}
bellmanFord(m<<1, n, 1);
printf ("%d\n", dis[n]);
}
return 0;
}



Floyed

/*
* fudq.cpp
*
* Created on: 2012-08-06
* Author: fudq
*/
#include<algorithm>
#include<stdio.h>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<stack>
#include<map>
#include<iostream>
using namespace std;
int n,m,p,q;
int f[110][110];

void floyed()
{
int i,j,k;
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(f[i][k]+f[k][j]<f[i][j])
f[i][j]=f[i][k]+f[k][j];
}
}
}
if(f[1][n]==999999)
printf("0\n");
else
printf("%d\n",f[1][n]);
}

int main()
{
int i,a,b,c;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0 && m==0)
break;
for(p=1;p<=n;p++)
{
for(q=1;q<=n;q++)
f[p][q]=999999;
}
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
f[a][b]=c;
f[b][a]=c;
}
floyed();
}
return 0;
}




SPFA

/*
* fudq.cpp
*
* Created on: 2012-08-06
* Author: fudq
*/
#include<algorithm>
#include<stdio.h>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<stack>
#include<map>
#include<iostream>
using namespace std;
#define MAX 999999999
#define N 1010
int dis[N],n,m;
int edge[N][N];
bool vis[N];

void SPFA(int s)
{
int i,u;
memset(vis,false,sizeof(vis));
for(i=1;i<=n;i++)
dis[i]=MAX;
queue<int>Q;
Q.push(s);
vis[s]=true;
dis[s]=0;
while(!Q.empty())
{
u=Q.front();
Q.pop();
vis[u]=false;
for(i=1;i<=n;i++)
{
if(dis[i]>dis[u]+edge[u][i])
{
dis[i]=dis[u]+edge[u][i];
if(!vis[i])
{
vis[i]=true;
Q.push(i);
}
}
}
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
#endif
int i,j,a,b,c;
while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
{
for(i=0;i<=1000;i++){
for(j=0;j<=i;j++)
{
edge[i][j]=MAX;
edge[j][i]=MAX;
}
}
for(i=0;i<m;i++)
{
scanf("%d %d %d",&a,&b,&c);
if(edge[a][b]>c)
{
edge[a][b]=c;
edge[b][a]=c;
}
}

SPFA(1);
printf("%d\n",dis[n]);
}
return 0;
}



  评论这张
 
阅读(144)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018