图论的经典入门题目：
一开始想用此题试试Mellman_ford算法，可是不料，直接TLE
最后改为SPFA，就过了，看来Mellman_ford算法不经优化，还是行不通的。。
不够至少通过这道题目认识了Mellman_ford算法：
Mellman_ford算法流程：
给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s，
数组Distant[i]记录从源点s到顶点i的路径长度，初始化数组Distant[n]为, Distant[s]为0；
以下操作循环执行至多n-1次，n为顶点数：
对于每一条边e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值；
若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的边，则图中存在负环路，即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。
ps:
1、单向还是双向图，考虑清楚
2、注意那个maxInt这个值超不超，够不够
3、注意是否两点间有多条路径
4、分清变量是double型的还是int型的
5、注意主函数中初始化map[][]中的点边不要搞错（注意所有初始化，正确命名好变量）
TEL代码(Mellman_ford算法):
| #include<iostream> using namespace std; const int maxNum=205; const int maxInt=99999999; typedef struct Edge { int u,v;//起点，终点 int weight;//权重 }Edge; Edge edge[maxNum];//保存边的值 int dist[maxNum];//结点到源点的最小距离 int nodeNum,edgeNum,start,end;//节点数，边数，起点，终点 //松弛计算 void relax(int u,int v,int weight) { if(dist[v]>dist[u]+weight) { dist[v]=dist[u]+weight; } } bool Bellman_Ford() { int i,j; for( i=0;i<nodeNum-1;i++) for( j=0;j<edgeNum;j++) { relax(edge[j].u,edge[j].v,edge[j].weight); } bool flag=1; //判断是否有负环，这道题目不存在负环，所以这个可以去掉 for( i=0;i<edgeNum;i++) if(dist[edge[i].v]>dist[edge[i].u]+edge[i].weight) { cout<<dist[edge[i].v]<<endl<<dist[edge[i].u]<<endl<<edge[i].weight<<endl; flag=0; break; } return flag; } int main(void) { int point,n,i; while(scanf("%d%d",&nodeNum,&edgeNum)==2) { for(i=0;i<nodeNum;i++) dist[i]=maxInt; for(i=0;i<edgeNum;i++) scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].weight); scanf("%d%d",&start,&end); dist[start]=0; if(edge[i].u==start) dist[edge[i].v]=edge[i].weight; if(Bellman_Ford()) { if(dist[end]==maxInt) printf("-1\n"); else printf("%d\n",dist[end]); } else { printf("-1\n"); } } return 0; } |
AC代码（SPFA算法）：
| #include<iostream> using namespace std; const int maxNum=205; const int maxInt=99999999; int map[maxNum][maxNum]; int dis[maxNum]; char vst[maxNum]; int nodeNum,edgeNum,start,end; int SPFA() { int i,pri,end,p,Q[maxNum]; memset(vst,0,sizeof(vst)); for( i=0;i<maxNum;i++) Q[i]=0; for(i=0;i<nodeNum;i++) dis[i]=maxInt; dis[start]=0; vst[start]=1; Q[0]=start; pri=0; end=1; while(pri<end) { p=Q[pri]; for(i=0;i<nodeNum;i++) { if(dis[p]+map[p][i]<dis[i]) { dis[i]=dis[p]+map[p][i]; if(!vst[i]) { Q[end++]=i; vst[i]=1; } } } vst[p]=0; pri++; } return 1; } int main(void) { int i,s,e,w,j; while(scanf("%d%d",&nodeNum,&edgeNum)==2) { for(i=0;i<nodeNum;i++) for(j=0;j<nodeNum;j++) { map[i][j]=maxInt; } for(i=0;i<edgeNum;i++) { scanf("%d%d%d",&s,&e,&w); if(map[s][e]>w) map[s][e]=map[e][s]=w; } scanf("%d%d",&start,&end); if(SPFA()) { if(dis[end]==maxInt) printf("-1\n"); else { printf("%d\n",dis[end]); } } else { printf("-1\n"); } } return 0; } |