bellman-ford.cpp

网络优化算法：任两点间最短路径问题的BellmanFord算法

// Bellman-Ford.cpp
// 任两点间最短路径问题的BellmanFord算法
// copyright: [e-mail],qq:13247899

#include "stdio.h"
#include "iostream.h"
#define Maxint 10000
#define CLength 6

int PrintMatrix(int n,int C[CLength][CLength])
{
	int i,j;

	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
		{
			if (C[i][j]!=Maxint)
				cout<<C[i][j]<<"\t";
			else
				cout<<"∞\t";
		}
		cout<<"\n";
	}
	return 1;
}

int PrintDist(int n,int dist[],int Curtime)
{
	int i,j;
	cout<<"第"<<Curtime<<"次迭代："<<"\n";
	
	for (i = 1; i <= n; i++)
	{
		if (dist[i]!=Maxint)
			cout<<dist[i]<<"\t";
		else
			cout<<"∞\t";		
	}
	cout<<"\n";
	return 1;
}

int BellmanFord(int n,int v,int dist[],int prev[CLength][CLength],int C[CLength][CLength],int resnet[CLength][CLength],int recurtime)
{
	// 运算正确返回0，若有负圈返回其中的一个节点
	// prev存储最短路 prev[i][j] 存储第i次迭代到节点j的中间最短点的更新
	// recurtime:迭代次数 ,一般计算n-1次,判断负圈计算n次;如果有负圈沿负圈增广resnet
	
	int i,j;
	int tempdist[CLength]={Maxint};
	for (i = 1; i <= n; i++)
	{
		tempdist[i]=dist[i]=C[v][i];
		prev[1][i]=v;
	}
	tempdist[v]=dist[v]=0;

	cout<<"\n";	
	PrintDist(n,dist,1);

	int cycleindex=0;
	for (int k = 2; k <= recurtime; k++)
	{
		int temp=Maxint;
		int newdist=Maxint;
		for (j = 1; j <= n ; j++) 
		{
			int minindex=0;
			temp=Maxint;
			for (i = 1; i <= n ; i++) 
				if ((i!=j)&&(i!=v)&&(C[i][j]<Maxint)) 
				{ 
					newdist=dist[i]+C[i][j];
					if(newdist<temp)
					{
						minindex=i;
						temp=newdist;
					}
				}
			if(temp<dist[j] )
			{
				tempdist[j]=temp;
				// n次迭代不收敛,说明有负圈,记下圈中的一个节点j
				if (k==n)
					cycleindex=j;
				prev[k][j]=minindex;
			}
			else
			{
				tempdist[j]=dist[j];
				prev[k][j]=prev[k-1][j];
			}
		}
		for (j = 1; j <= n ; j++) 
			dist[j]=tempdist[j];
		PrintDist(n,dist,k);
	}

	cout<<"\n";

	if (cycleindex!=0)
	{
		// 输出负圈
	}
	
	return cycleindex;
}

void ShortRBF(int n,int v,int dist[],int prev[CLength][CLength])
{
	int i,j;
	for (i = 1; i <= n ; i++)
	{
		if(i==v)
			continue;
		if (dist[i]==Maxint)
			cout<<endl<<"顶点"<<v<<"到顶点"<<i<<"无路可达！";
		else
		{
			cout<<"顶点"<<v<<"到顶点"<<i<<"的最短距离为："<<dist[i]<<endl;
			cout<<"顶点"<<v<<"到顶点"<<i<<"的最短路径为："<<endl;
			j=prev[n-1][i];
			cout<<i<<"<-";
			for(int ii=n-1;ii>0;ii--)
			{
				if(prev[ii][j]!=j && prev[ii][j]!=0)
					cout<<j<<"<-";
				else if(prev[ii][j]==0)
					continue;
				j=prev[ii][j];
			}
			cout<<v<<endl<<endl;
		}
	}
}

void main(void)
{
/*	int resCost[CLength][CLength]={ 
		{0,0,0,0,0,0},
		{0,0,     10,    Maxint,30,    100,  },
		{0,Maxint,0,     50,    Maxint,Maxint},
		{0,Maxint,Maxint,0,     Maxint,10    },
		{0,Maxint,Maxint,20,    0,     60    },
		{0,Maxint,Maxint,Maxint,Maxint,0     },
	};*/

/*	// p133
	int resCost[CLength][CLength]={ 
		{0,0,0,0,0,0},
		{0,0,     1,     5,		Maxint,3,    },
		{0,Maxint,0,     2,     Maxint,Maxint},
		{0,Maxint,Maxint,0,     Maxint,-4    },
		{0,Maxint,Maxint,2 ,    0,     Maxint},
		{0,Maxint,Maxint,Maxint,3,     0     },
	};
*/
	int resCost[CLength][CLength]={ 
		{0,0,0,0,0,0},
		{0,0,     1,     Maxint,     Maxint,5},
		{0,Maxint,0,     -3,         Maxint,3},
		{0,Maxint,Maxint,0,     3,Maxint	 },
		{0,Maxint,Maxint,Maxint,    0     ,2},
		{0,Maxint,Maxint,-3,Maxint,     0     },
	};

/*	int resCost[CLength][CLength]={ 
		{0, 0, 0, 0,0},
		{0, 0, 1, Maxint-100,Maxint-100},
		{0,-1, 0, 2,5},
		{0,-2,-2, 0,1},
		{0, Maxint-100,-5,-1,0},
	};
		int resCost[CLength][CLength]={ 
		{0, 0, 0, 0,0},
		{0, Maxint, Maxint, 2,         Maxint},
		{0,-1,          Maxint, 2,         5},
		{0,-2,          Maxint, Maxint,1},
		{0, Maxint,-5,         -1,         Maxint}};*/

	int i,j;


	int dist[CLength]={0},prev[CLength][CLength],v=1,n=CLength-1;
	PrintMatrix(n,resCost);

	int resnet[CLength][CLength]={0};

	BellmanFord(n,v,dist,prev,resCost,resnet,n-1);
	ShortRBF(n,v,dist,prev);
}