main.cpp

最短路径法 学习数据结构时本人用C++编写的

#include<iostream.h>
typedef int vextype;
struct edgenode
{
	int adjvex;
	float length;
	edgenode *next;
};
struct vexnode
{
	vextype vertex;
	edgenode *link;
};
struct edge
{
	int fromvex,endvex;
	float length;
};
int n;
vexnode *Createtable()
{	
	int i,j;
	float length;
	edgenode *s;
	vexnode *graph;
	cout<<"输入图中结点个数！"<<endl;
	cin>>n;
	graph=new vexnode [n];
	for(i=0;i<n;i++)
	{
		graph[i].vertex=i+1;
		graph[i].link=NULL;
	}
	cout<<"输入点之间的联结信息 权为-1结束输入!"<<endl;
	cin>>i;
	cin>>j;
	cin>>length;
	while(length>-1)
	{
		s=new edgenode;
		s->adjvex=j;
		s->length=length;
		s->next=graph[i-1].link;
		graph[i-1].link=s;
		//s=new edgenode;
	//	s->adjvex=i;
	//	s->next=graph[j-1].link;
	//	s->length=length;
	//	graph[j-1].link=s;
		cout<<"输入点之间的联结信息 权为-1结束输入!"<<endl;
		cin>>i;
		cin>>j;
		cin>>length;
		
	}
	return graph;
}
edgenode * search(edgenode  *p,int v)
{
	while(p)
	{
		if(p->adjvex==v)
			return p;
		else 
			p=p->next;
	}
	return NULL;
}
main()
{
	edgenode *p;
	vextype *P,*S,pre;
	float *D,min,max=1000,inf=1100,length;
	int v,i,j,k,v1;
	vexnode *graph;
	graph=Createtable();
	P=new vextype [n];
	S=new vextype [n];
	D=new float [n];
	
	cout<<"输入出发点号！,输入负数结束输入！"<<endl;
	cin>>v;
	v1=v-1;
	while(v>=0)

	{
		for(i=0;i<n;i++)
		{
			p=graph[v1].link;
			if(p&&(p=search(p,i+1)))
			{
				D[i]=p->length;
				P[i]=v;
			}
			else
			{	
				D[i]=max;
				P[i]=0;
			}
		}
		for(i=0;i<n;i++) S[i]=0;
		S[v1]=1;D[v1]=0;
		for(i=0;i<n-1;i++)
		{
			min=inf;
			for(j=0;j<n;j++)
				if((!S[j])&&(D[j]<min))
				{
					min=D[j];
					k=j;
				}
			S[k]=1;
			for(j=0;j<n;j++)
			{	
				p=graph[k].link;
				if(p&&(p=search(p,j+1)))
					length=p->length;
				else
					length=max;
				if((!S[j])&&(D[j]>D[k]+length))
				{
					D[j]=D[k]+length;
					P[j]=k+1;
				}
			}
		}
		for(i=0;i<n;i++)
		{
			cout<<"起始点："<<v<<"权值："<<D[i]<<",尾点："<<i+1<<"路径："<<i+1;
			pre=P[i];
			while(pre!=0)
			{
				cout<<"<---"<<pre;
				pre=P[pre-1];
			}
			cout<<endl;
		}

	cout<<"输入出发点号！,输入负数结束输入！"<<endl;
	cin>>v;
	v1=v-1;
	}
	return 0;	
}