最短路径-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 更新，感谢观看^-

---