修改一次边称为一次松弛.
下面给出测试数据,第一行是顶点个数n,,然后输入每条边的数据,格式为u,v,w分别表示这条边的起点,终点和权值,顶点从0开始记起,最后一行为-1 -1 -1 ,表示数据输入的结束.
将数据保存为in.txt与源代码放在同一目录下.
/*we start 0 */ #include<iostream> #include<cstdio> #include<cstring> using namespace std; #define INF 1000000 #define MAXN 10 int n; int edge[MAXN][MAXN]; int dist[MAXN]; int path[MAXN]; /*Bellman algorithm hell * init the function * here,the meaning of expression of dist[] and path[] * dist[] is distance ,path[2]=0 means vertex 0 to vertex 2 directed way the vertex 0 is fronter,else is -1 */ void Bellman(int v0) { int i,j,k,u;//k是表示从源点到各点的线路条数,u就是从0到那个顶点 for(i=0;i<n;i++) { dist[i]=edge[v0][i];//将第一个源点到各点的距离写入dist[i] if(i!=v0 && dist[i]<INF)//将与v0有直接关系的顶点的path值改写 path[i]=v0; else /*其余各点为-1*/ path[i]=-1; } /*从dist(1)[u]递推出dist(2)[u],dist(3)[u]....dist(n-1)[u]*/ for(k=2;k<n;k++) { /*修改每个顶点的dist[u]和path[u]*/ for(u=0;u<n;u++) { if(u!=v0) { /*考虑其他每个顶点*/ for(j=0;j<n;j++) { /*顶点j到顶点u有直接路径....*/ if(edge[j][u]<INF && dist[j]+edge[j][u]<dist[u]) { /*这一步称为松弛:Slack,to be honst,我不理解 * 课本上这样说:Bellman-ford的算法的本质是对 * 每条边进行判断,设边的权值为w(j,u),在这里 * 就是edge[j][u],如果边w(j,u)的引入会使得 * dist`[u]的值减小即将dist[j]+edge[j][u]赋给dist[u] * ,那么前一句 * edge[j][u]<INF * 就是 * 说可以引入边w(j,u)*/ dist[u]=dist[j]+edge[j][u]; path[u]=j; } } } } } } int main() { freopen("in.txt","r",stdin); int u,v,w,i,j; cin>>n; // memset(edge,0,sizeof(edge)); while(1) { scanf("%d%d%d",&u,&v,&w); if(u==-1 && v==-1 && w==-1) break; edge[u][v]=w; } for(i=0;i<n;i++) for(j=0;j<n;j++) { if(i==j) edge[i][j]=0; else if(edge[i][j]==0) edge[i][j]=INF; } Bellman(0); int shortest[MAXN]; /*在这里运用了倒向追踪的方法,That‘s what?*/ for(i=1;i<n;i++) { printf("%d\t",dist[i]);//输出各顶点时存放的序号 memset(shortest,0,sizeof(shortest)); int k=0;// shortest[k]=i; while(path[shortest[k]]!=0) { k++; shortest[k]=path[shortest[k-1]]; } k++; shortest[k]=0; for(j=k;j>0;j--) printf("%d-->",shortest[j]); printf("%d\n",shortest[0]); } return 0; }测试数据:
7 0 1 6 0 2 5 0 3 5 1 4 -1 2 1 -2 2 4 1 3 2 -2 3 5 -1 4 6 3 5 6 3 -1 -1 -1
运行结果如下:
Bellman-ford 代码实现,布布扣,bubuko.com
原文:http://blog.csdn.net/yuzibo747/article/details/20391335