Bellman 算法实现

 

样例输入：
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

样例输出
1 0→3→2→1
3 0→3→2
5 0→3
0 0→3→2→1→4
4 0→3→5
3 0→3→2→1→4→6

 

 

#include <stdio.h> #include <string.h> #define INF 1000000 //无穷大 #define MAXN 20 //顶点个数最大值int n; //顶点个数 int Edge[MAXN][MAXN]; //邻接矩阵 int dist[MAXN]; // int path[MAXN]; // void Bellman( int v0 ) //求顶点v0到其他顶点的最短路径 {int i, j, k, u; //循环变量for( i=0; i<n; i++ )//初始化 {dist[i] = Edge[v0][i];if( i!=v0 && dist[i]<INF ) path[i] = v0;else path[i] = -1;}for( k=2; k<n; k++ ) //从dist(1)[u]递推出dist(2)[u], …,dist(n-1)[u] {for( u=0; u<n; u++ ) //修改每个顶点的dist[u]和path[u] {if( u != v0 ){for( j=0; j<n; j++ )//考虑其他每个顶点 {//顶点j到顶点u有直接路径，且途经顶点j可以使得dist[u]缩短if( Edge[j][u] < INF && dist[j] + Edge[j][u] < dist[u] ){dist[u] = dist[j] + Edge[j][u];path[u] = j;}}//end of for}//end of if}//end of for}//end of for }int main( ) {int i, j; //循环变量int u, v, w; //边的起点和终点及权值scanf( "%d", &n ); //读入顶点个数nwhile( 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 ); //求顶点0到其他顶点的最短路径int shortest[MAXN]; //输出最短路径上的各个顶点时存放各个顶点的序号for( i=1; i<n; i++ ){printf( "%d\t", dist[i] ); //输出顶点0到顶点i的最短路径长度//以下代码用于输出顶点0到顶点i的最短路径memset( shortest, 0, sizeof(shortest) );int k = 0; //k表示shortest数组中最后一个元素的下标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; }

 用vertor实现Bellman:

#include<iostream> #include<vector> using namespace std; const int N = 100; const int INF = 0x3f3f3f3f;struct Edge{ //用于记录一组关系int u,v,w; };vector<Edge> edge; //用于保存图的关系 int dis[N]; //源点到各点的最短距离 int path[N]; //源点到各点的路径 int road[N]; //用于逆向追中输出路径void init(){while(!edge.empty()){edge.clear();} }void Bellman_Ford_vector(int v,int n,int m){ //源点,定点数，边数int i,j;memset(path,255,sizeof(path)); //初始化路径为-1;for(i=0;i<=n;i++){ //初始化dis[i]为不可到达dis[i] = INF;}dis[v] = 0; //把源点到自己的路径改为0for(i=0;i<n;i++){ //第一层循环，由dis0递推出dis1~nfor(j=0;j<m;j++){ //判断边<u,v>的引入能否缩短源点到v的距离if(dis[edge[j].u] + edge[j].w < dis[edge[j].v]){ //若可以松弛，更新dis[edge[j].v] = dis[edge[j].u] + edge[j].w;path[edge[j].v] = edge[j].u;}}} }int main(){freopen("in.txt","r",stdin);int n;Edge temp;while(scanf("%d",&n)!=EOF){init();while(scanf("%d%d%d",&temp.u,&temp.v,&temp.w) && ~temp.u && ~temp.v && ~temp.w){edge.push_back(temp); //把关系添加到vector }Bellman_Ford_vector(0,n,edge.size());for(int i=1;i<n;i++){printf("%d\t",dis[i]); //输出最短路int k=0; //用于标记要经过几个点road[k] = i; //保存第一个点while(path[road[k]] != -1){//若还有前继点，逆向追踪k++;road[k] = path[road[k-1]];}while(k){ //输出路径printf("%d->",road[k--]);}printf("%d\n",road[k]);}}return 0; }

 

转载于:https://www.cnblogs.com/Deng1185246160/p/3223236.html

总结

以上是生活随笔为你收集整理的Bellman 算法实现的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。