hdu 2544
Dijkstra
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define maxn 110
#define inf 0x3f3f3f3f3f
struct Edge
{
int from,to,dist;
}Map[11000];
int a[maxn][maxn];
int d[maxn];
int visit[maxn];
int n,m;
void init()
{
memset(visit,0,sizeof(visit));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
a[i][j]=inf;
if(i==j)
a[i][j]=0;
}
for(int i=2;i<=maxn;i++)
d[i]=inf;
d[1]=0;
}
void Dijkstra()
{
for(int k=1;k<=n;k++) //循环n次是因为每次都找到了一个距离源点最近的点,n次就找完了所有距离源点最近的点,可以看成有两个集合,一个集合代表已找出距离源点最近的点,一个是还未找出的点
{
int m=inf;
int x;
for(int i=1;i<=n;i++) //暴力枚举未找出最小距离的点中的与源点相连的最小距离的点
{
if(!visit[i] && d[i]<m)
{
x=i;
m=d[i];
}
}
visit[x]=1;
for(int i=1;i<=n;i++) //更新
{
if(a[x][i]!=inf)
d[i]=min(d[i],d[x]+a[x][i]);
}
}
// for(int i=1;i<=n;i++)
// printf("%d ",d[i]);
// cout<<endl;
printf("%d
",d[n]);
}
int main()
{
while(~scanf("%d%d",&n,&m) && n!=0 && m!=0)
{
init();
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&Map[i].from,&Map[i].to,&Map[i].dist);
a[Map[i].from][Map[i].to]=Map[i].dist;
a[Map[i].to][Map[i].from]=Map[i].dist;
}
Dijkstra();
}
// system("pause");
return 0;
}
Dijkstra(优先队列优化,优化的是每次选取距离源点最近的点，裸的是暴力枚举)
Dijkstra使用优先队列，虽然同一个点可以多次入队(因为每个节点都可以被其他节点多次刷新)，但是done数组保证了一个点真正pop出来刷新其他点的时候只有一次
当第一次出队去更新别人的时候，done[i]=true，之后判断一下就可以了。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <queue> using namespace std; #define maxn 110 #define inf 0x3f3f3f3f3f3f struct Edge { int from,to,dist; }; vector <int> G[maxn*4]; //存图的编号 vector <Edge> edges; int d[maxn]; int visit[maxn]; //标记是否在队列里 int n,m; priority_queue < int > q; void init() { for(int i=0;i<=n;i++) G[i].clear(); edges.clear(); memset(visit,0,sizeof(visit)); for(int i=1;i<=n;i++) d[i]=inf; d[1]=0; } void AddEdge(int from,int to,int dist) { Edge edge; edge.from=from; edge.to=to; edge.dist=dist; edges.push_back(edge); int SIZE=edges.size(); G[from].push_back(SIZE-1); } void Dijkstra() //由于每次出队的都是最小值,保证每个节点只进队一次。 { q.push(1); while(!q.empty()) { int x=q.top(); q.pop(); for(int i=0;i<G[x].size();i++) { Edge e=edges[G[x][i]]; if(d[e.to]>d[e.from]+e.dist) { d[e.to]=d[e.from]+e.dist; q.push(e.to); } } } // for(int i=1;i<=n;i++) // printf("%d ",d[i]); // cout<<endl; printf("%d ",d[n]); } int main() { while(~scanf("%d%d",&n,&m) && n!=0 && m!=0) { init(); for(int i=1;i<=m;i++) { int from,to,dist; scanf("%d%d%d",&from,&to,&dist); AddEdge(from,to,dist); AddEdge(to,from,dist); } Dijkstra(); } // system("pause"); return 0; }
Bellman_ford(图解最短路 http://www.java3z.com/cwbwebhome/article/article1/1359.html?id=4720 )
d[k][Map[i].to]=d[k-1][Map[i].from]+Map[i].dist;
#include <iostream>
#include <cstdio>
#include <cstring >
using namespace std;
#define maxn 110
#define inf 0x3f3f3f3f3f
struct Edge
{
int from,to,dist;
}Map[200010];
int d[maxn][maxn];
int n,m;
void init()
{
for(int k=0;k<maxn;k++)
for(int i=1;i<maxn;i++)
d[k][i]=inf;
for(int k=0;k<maxn;k++)
d[k][1]=0;
}
void Bellman_foyed()
{
//对每条边进行n次松弛操作
// cout<<"fsdfsd";
for(int k=1;k<=n;k++)
{
for(int i=1;i<=m;i++)
{
if(d[k-1][Map[i].from]<inf)
if(d[k-1][Map[i].from]+Map[i].dist<d[k][Map[i].to])
{
d[k][Map[i].to]=d[k-1][Map[i].from]+Map[i].dist;
}
}
}
/*for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
printf("%d ",d[k][i]);
printf("
");
}*/
printf("%d
",d[n][n]);
}
int main()
{
while(~scanf("%d%d",&n,&m) && n!=0 && m!=0)
{
init();
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&Map[i].from,&Map[i].to,&Map[i].dist);
// cin>>Map[i].from>>Map[i].to>>Map[i].dist;
}
for(int i=m+1;i<=2*m;i++)
{
Map[i].to=Map[i-m].from;
Map[i].from=Map[i-m].to;
Map[i].dist=Map[i-m].dist;
}
m=2*m;
Bellman_foyed();
}
//getchar();
return 0;
}
Bellman_ford 邻接表
d[k][Map[i].to]=d[k-1][Map[i].from]+Map[i].dist;(省略了k这一维，可以理解成一个节点被其他节点刷新n次)
#include <iostream>
#include <cstdio>
#include <cstring >
using namespace std;
#define maxn 110
#define inf 0x3f3f3f3f3f
struct Edge
{
int from,to,dist;
}Map[200010];
int d[maxn];
int n,m;
void init()
{
for(int i=1;i<maxn;i++)
d[i]=inf;
d[1]=0;
}
void Bellman_foyed()
{
//对每条边进行n次松弛操作
// cout<<"fsdfsd";
for(int k=1;k<=n;k++)
{
for(int i=1;i<=m;i++)
{
if(d[Map[i].from]<inf)
if(d[Map[i].from]+Map[i].dist<d[Map[i].to])
{
d[Map[i].to]=d[Map[i].from]+Map[i].dist;
}
}
}
/*for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
printf("%d ",d[k][i]);
printf("
");
}*/
printf("%d
",d[n]);
}
int main()
{
while(~scanf("%d%d",&n,&m) && n!=0 && m!=0)
{
init();
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&Map[i].from,&Map[i].to,&Map[i].dist);
// cin>>Map[i].from>>Map[i].to>>Map[i].dist;
}
for(int i=m+1;i<=2*m;i++)
{
Map[i].to=Map[i-m].from;
Map[i].from=Map[i-m].to;
Map[i].dist=Map[i-m].dist;
}
m=2*m;
Bellman_foyed();
}
//getchar();
return 0;
}
Bellman_ford 邻接矩阵(一个节点被刷新n次)
d[k][i]代表从源点经过k个点，或者说是k条边的最短距离。
d[k][i]=min(d[k][i],d[k-1][j]+a[j][i]);
#include <iostream>
#include <cstdio>
#include <cstring >
using namespace std;
#define maxn 110
#define inf 0x3f3f3f3f3f
int a[maxn][maxn];
int d[maxn][maxn][maxn];
int n,m;
void init()
{
for(int k=0;k<maxn;k++)
for(int i=0;i<maxn;i++)
for(int j=0;j<maxn;j++)
{
a[i][j]=inf;
d[k][i][j]=inf;
if(i==j)
d[k][i][j]=0;
}
}
void Bellman_foyed()
{
//对每条边进行2*m次松弛操作
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j && a[j][i]!=inf)
{
if(d[k-1][1][j]+a[j][i]<d[k][1][i])
{
d[k][1][i]=d[k-1][1][j]+a[j][i];
}
}
}
}
}
/* for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
printf("%d ",d[k][1][i]);
printf("
");
}*/
printf("%d
",d[n][1][n]);
}
int main()
{
while(~scanf("%d%d",&n,&m) && n!=0 && m!=0)
{
init();
int from,to,dist;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&from,&to,&dist);
a[from][to]=dist;
// d[from][to]=dist;
a[to][from]=dist;
// d[to][from]=dist;
}
Bellman_foyed();
}
return 0;
}
spfa
visit数组 检查被更新的节点，保证队列里面没有相同节点，但是一个节点可以进队列多次
用SPFA的时侯，同一个节点可能会多次入队，然后多次去刷新其他节点，这样就会导致最短路条数出现重复计算（所以才可以判断负环）
当每个节点只进队列一次的话，退化成宽搜。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
using namespace std;
#define maxn 110
#define inf 0x3f3f3f3f3f3f
struct Edge
{
int from,to,dist;
};
vector <int> G[maxn*4]; //存图的编号
vector <Edge> edges;
int d[maxn];
int visit[maxn]; //标记是否在队列里
int n,m;
queue < int > q;
void init()
{
for(int i=0;i<=n;i++)
G[i].clear();
edges.clear();
memset(visit,0,sizeof(visit));
for(int i=1;i<=n;i++)
d[i]=inf;
d[1]=0;
}
void AddEdge(int from,int to,int dist)
{
Edge edge;
edge.from=from; edge.to=to; edge.dist=dist;
edges.push_back(edge);
int SIZE=edges.size();
G[from].push_back(SIZE-1);
}
void spfa()
{
q.push(1);
visit[1]=1;
while(!q.empty())
{
//cout<<"fsdf"<<endl;
int x=q.front();
q.pop();
visit[x]=0;
for(int i=0;i<G[x].size();i++)
{
int next_=G[x][i]; //
if(d[edges[next_].to]>d[edges[next_].from]+edges[next_].dist && d[edges[next_].from]<inf)
{
d[edges[next_].to]=d[edges[next_].from]+edges[next_].dist;
if(visit[edges[next_].to]==0)
{
visit[edges[next_].to]=1;
q.push(edges[next_].to);
}
}
}
}
//for(int i=1;i<=n;i++)
// printf("%d ",d[i]);
//cout<<endl;
printf("%d
",d[n]);
}
int main()
{
while(~scanf("%d%d",&n,&m) && n!=0 && m!=0)
{
init();
for(int i=1;i<=m;i++)
{
int from,to,dist;
scanf("%d%d%d",&from,&to,&dist);
AddEdge(from,to,dist);
AddEdge(to,from,dist);
}
spfa();
}
// system("pause");
return 0;
}
floyd
#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define maxn 110 #define inf 0x3f3f3f3f3f3f int n,m; int Map[maxn][maxn]; int d[maxn][maxn][maxn]; void init() { for(int i=0;i<maxn;i++) for(int j=0;j<maxn;j++) { Map[i][j]=inf; if(i==j) Map[i][j]=0; } } void floyd() { for(int i=0;i<maxn;i++) for(int j=0;j<maxn;j++) d[0][i][j]=Map[i][j]; for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[k][i][j]=min(d[k-1][i][j],d[k-1][i][k]+d[k-1][k][j]); /* for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) printf("%d ",d[i][j]); printf(" "); }*/ printf("%d ",d[n][1][n]); } int main() { while(scanf("%d%d",&n,&m) && n!=0 && m!=0) { init(); int from,to,dist; for(int i=1;i<=m;i++) { scanf("%d%d%d",&from,&to,&dist); Map[from][to]=dist; Map[to][from]=dist; } floyd(); } return 0; }