最短路径-Bellman Ford算法
2021/7/16 14:06:12
本文主要是介绍最短路径-Bellman Ford算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
最短路径-Bellman Ford算法
这里采用邻接矩阵实现Bellman Ford算法;可以参考blog;
限于时间,暂时只写下代码,以后有时间补上…
代码
- 采用邻接矩阵,代码没有通过,不清错错在哪边,如果有大佬发现错误,欢迎留言我的邮箱ycqnfz@gmail.com
感觉用边节点表示比较简单…
#include<iostream> #include<cstring> #define clr(x) memset(x,0,sizeof(x)) #define maxn 1000+5 using namespace std; const int maxint=1<<(sizeof(int)*8-1)-1; int n,m,k; //点数,边数 int mp[maxn][maxn]; int dis[maxn],path[maxn]; void chushihua() { cin>>n>>m>>k; for(int i=0; i<=n; i++) for(int j=1; j<=n; j++) mp[i][j]=maxint; for(int i=0; i<m; i++) { int v1,v2,w; cin>>v1>>v2>>w; mp[v1][v2]=w; } } //Bellman Ford算法 bool solve(int s,int t) { for(int i=1; i<=n; i++) { dis[i]=mp[s][i]; if(i!=s && dis[i]<maxint) path[i]=s; //当前不是起点并且可以到达,设前驱位起点s else path[i]=-1; } // for(int i=0;i<n;i++) cout<<path[i]<<" \t"<<dis[i]<<endl; for(int i=0; i<k-1; i++) { for(int u=1; u<=n; u++) { if(u==s) continue; for(int v=1; v<=n; v++) { if(mp[v][u]<maxint && dis[u]>dis[v]+mp[v][u]) { dis[u]=dis[v]+mp[v][u]; path[u]=v; } } } // for(int j=1; j<=n; j++) cout<<dis[j]<<" "; cout<<endl; // for(int j=1; j<=n; j++) cout<<path[j]<<" ";cout<<endl; } if(dis[t]>maxint/2) return false; //不可到t else return true; } int main() { chushihua(); if(solve(1,n)) cout<<dis[n]<<endl; else cout<<"impossible"<<endl; return 0; }
以下示例没有通过:
10 20 8
4 2 7
8 7 10
1 3 1
7 6 1
4 5 8
8 7 5
5 7 1
6 10 2
3 1 9
5 4 4
4 7 1
9 9 9
8 1 8
5 4 5
7 6 5
3 7 7
4 9 1
2 1 9
2 9 9
6 1 -2
11
- 采用边节点表示图仿写的代码,代码通过:
#include<iostream> #include<cstring> #define clr(x) memset(x,0,sizeof(x)) #define maxn 10000+5 using namespace std; const int maxint=1<<(sizeof(int)*8-1)-1; typedef struct Edge { int v1,v2; int w; void show() { cout<<"u="<<v1<<"\tv="<<v2<<"\tw="<<w<<endl; } } Edge; int n,m,k; Edge edges[maxn]; int dis[maxn],path[maxn]; void chushihua() { cin>>n>>m>>k; for(int i=1; i<=m; i++) { int v1,v2,wei; cin>>v1>>v2>>wei; edges[i].v1=v1; edges[i].v2=v2; edges[i].w=wei; } } bool solve(int s,int t) { for(int i=1; i<=n; i++) dis[i]=maxint; dis[s]=0; for(int i=0; i<k; i++) { int tmp[maxn]; for(int j=1; j<=n; j++) tmp[j]=dis[j]; for(int j=1; j<=m; j++) { int v1=edges[j].v1, v2=edges[j].v2, w=edges[j].w; if(dis[v2]>tmp[v1]+w) { // edges[j].show(); dis[v2]=tmp[v1]+w; path[v2]=v1; } } } if(dis[t]>=maxint/2) return false; else return true; } int main() { chushihua(); if(solve(1,n)) cout<<dis[n]<<endl; else cout<<"impossible"<<endl; return 0; }
2021-06-1 更新,感谢观看-
这篇关于最短路径-Bellman Ford算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-02Java管理系统项目实战入门教程
- 2024-11-02Java监控系统项目实战教程
- 2024-11-02Java就业项目项目实战:从入门到初级工程师的必备技能
- 2024-11-02Java全端项目实战入门教程
- 2024-11-02Java全栈项目实战:从入门到初级应用
- 2024-11-02Java日志系统项目实战:初学者完全指南
- 2024-11-02Java微服务系统项目实战入门教程
- 2024-11-02Java微服务项目实战:新手入门指南
- 2024-11-02Java项目实战:新手入门教程
- 2024-11-02Java小程序项目实战:从入门到简单应用