shortpath.txt

图的最短路径

#include <iostream.h>
#define VEXTYPE int 
#define ADJTYPE int 
#define MAXLEN 50
#define MAX 10000 //10000为∞
typedef struct 
{
	VEXTYPE vexs[MAXLEN];
	ADJTYPE arcs[MAXLEN][MAXLEN];
	int vexnum,arcnum;
	int kind;
}M_GRAPH;


M_GRAPH creat_mgraph()
{
	int i,j,k,h;
	M_GRAPH mg;
	mg.kind=3;
	cout<<"请输入顶点数：";
	cin>>mg.vexnum;
	cout<<"请输入边数:";
	cin>>mg.arcnum;
	for(i=0;i<mg.vexnum;i++)
	{
		cout<<"请输入第"<<i+1<<"个顶点信息:";
		cin>>mg.vexs[i];
	}
	for(i=0;i<mg.vexnum;i++)
		for(j=0;j<mg.vexnum;j++)
			mg.arcs[i][j]=MAX;
	for(k=1;k<=mg.arcnum;k++)
	{
		cout<<endl<<"第"<<k<<"条边的起始顶点编号:";
		cin>>i;
		cout<<endl<<"第"<<k<<"条边的终止顶点编号:";
		cin>>j;
		while(i<1||i>mg.vexnum||j<1||j>mg.arcnum)
		{
			cout<<"编号超出范围，重新输入："<<endl;
			cout<<endl<<"第"<<k<<"条边的起始顶点编号:";
			cin>>i;
			cout<<endl<<"第"<<k<<"条边的终止顶点编号:";
			cin>>j;
		}
		cout<<"此边的权值是:";
		cin>>h;
		mg.arcs[i-1][j-1]=h;
	}
	return mg;
}

void main()
{
	M_GRAPH mg;
	int cost[MAXLEN][MAXLEN];
	int path[MAXLEN],s[MAXLEN];
	int dist[MAXLEN];
	int i,j,n,v0,min,u;
	mg=creat_mgraph();
	cout<<"请输入起始顶点的编号:";		//有向图中顶点的编号从1编起
	cin>>v0;
	v0--;
	n=mg.vexnum;
	for(i=0;i<n;i++)				//cost矩阵初始化
	{
		for(j=0;j<n;j++)
			cost[i][j]=mg.arcs[i][j];
		cost[i][i]=0;
	}
	for(i=0;i<n;i++)
	{
		dist[i]=cost[v0][i];
		if(dist[i]<MAX&&dist[i]>0)		//dist数组初始化
			path[i]=v0;			//path数组初始化(全为0)
	}
	for(i=0;i<n;i++)
		s[i]=0;			//s数组初始化
	s[v0]=1;
	for(i=0;i<n;i++)
	{
		min=MAX;
		u=v0;
		for(j=0;j<n;j++)
			if(s[j]==0&&dist[j]<min)
			{
				min=dist[j];
				u=j;
			}
		s[u]=1;
		for(j=0;j<n;j++)
			if(s[j]==0&&(dist[u]+cost[u][j])<dist[j])
			{
				dist[j]=dist[u]+cost[u][j];
				path[j]=u;		//path记录了
			}
	}
	for(i=0;i<n;i++)
	{
		if(s[i]==1)
		{
			u=i;
			while(u!=v0)
			{
				cout<<u+1;
				u=path[u];
			}
			cout<<u+1;
			cout<<" d="<<dist[i]<<endl;    //有路径
		}
		else
			cout<<i+1<<"<-"<<(v0+1)<<" d=MAX"<<endl;	//无路径
	}
}