• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

求任意权值最短路径的Bellman-Ford算法C++实现

OC/C/C++ 水墨上仙 1435次浏览

求任意权值最短路径的Bellman-Ford算法C++实现
Bellman-Ford算法可以用来解决所要求的最短路径的图中含有负数边的情形。
算法的基本思想:如果两个结点间存在最短路径,那么这条路径中各个结点最多经过一次(因为如果超过一次,说明路径中有环,如果是正数环,会使路径权值增长;若为负数环,最短路径不存在;若为零环,不影响结果)。因此我们只需迭代n-1次,将起始点到其他各点最多经过n-1条边的最短路径求出来即可。
来源:http://blog.csdn.net/iqrocket/article/details/8305759

#include <iostream>
using namespace std;
const int MaxSize=10;
int arr[MaxSize][MaxSize]; 
int dist[MaxSize]; //保存起点到各结点最短路径的数组
int path[MaxSize]; //数组元素保存最短路径中经过的前一个结点
int numNode=0;
void createArr()
{
	cin>>numNode;
	for(int i=0;i<numNode;++i)
		for(int j=0;j<numNode;++j)
			cin>>arr[i][j];
}
//计算任意权值的最短路径的Bellman-Ford算法
//从顶点v找到所有其他定点的最短路径
void BellmanFord(const int v)
{
	//dist数组和path数组的初始化
	for(int i=0;i<numNode;++i)
	{
		dist[i]=arr[v][i];
		if(i!=v)
			path[i]=v;
		else
			path[i]=-1;
	}
	//最多迭代n-1次
	for(int len=2;len<numNode;++len)
		for(int u=0;u<numNode;++u)
			if(u!=v)
			{
				//每次都以u为终点,看以i为中转点到达u的总权值是否比dist[u]小,
				//小的话改写dist[u]
				for(int i=0;i<numNode;++i)
					if(dist[u]>dist[i]+arr[i][u])
					{
						dist[u]=dist[i]+arr[i][u];
						path[u]=i;
					}
			}
	
	//输出起始结点到各结点的最短路径
	for(int i=0;i<numNode;++i)
		cout<<dist[i]<<" ";
	cout<<endl;
	//输出最后一个结点最短路径经过的各结点(其他结点可用类似做法)
	int end=numNode-1;
	while(path[end]!=-1)
	{
		cout<<path[end]<<" ";
		end=path[end];
	}
	cout<<endl;
}
int main()
{
	createArr();
	BellmanFord(0);
}


喜欢 (0)
加载中……