short.c

键盘输入顶点信息

#include<stdio.h>
#include<stdlib.h>
#define M 100    //最大的顶点数
#define Maxint 32767
enum boolean{FALSE,TRUE};
typedef char VertexType;
typedef int Adjmatrix;
typedef struct{
	int  vexs[M];//顶点数组
    Adjmatrix arcs[M][M];//邻接矩阵
}MGraph;
int D1[M],P1[M],q[M],p1[M];
int D[M][M],P[M][M];//D表示路径，P表示两点之间权值
int i,c,j,g;  



void CreateMGraph(MGraph * G,int n,int e)//采用邻接矩阵表示法构造有向图G
{
	int i,j,k,w;//n,e表示土的当前顶点数和边数
for(i=1;i<=n;i++)
G->vexs[i]=i;
for(i=1;i<=n;i++)//输入顶点信息
   for(j=1;j<=n;j++)
   G->arcs[i][j]=Maxint;//初始化邻接距阵
   printf("输入%d条边的信息:\n",e);
  printf("起点 终点 权值用空格符分隔:\n"); 
for(k=1;k<=e;k++)//读入e条边，建立邻接距阵
{   
	printf("输入第%d条边信息\n",k);
 
	scanf("%d %d %d",&i,&j,&w);
     G->arcs[i][j]=w;
}
printf("有向图的存取结构建立完毕！\n");
}







void Dijkstra1(MGraph *G,int v,int n)
{

				if(v>n || v==0)  
				{
					printf("输入不正确\n");
					return ;
				}
				for(i=1;i<=n;i++)
				{
					p1[i]=v;
				}
				for(c=1;c<=n;c++)
					for(i=1;i<=n;i++)
						if(G->arcs[v][i]>G->arcs[v][c]+G->arcs[c][i])
						{
							G->arcs[v][i]=G->arcs[v][c]+G->arcs[c][i];
							p1[i]=c;
						}
						for(i=1;i<=n;i++)
						{
							if(v!=i)
							{
							if(G->arcs[v][i]==Maxint) 
							{
								printf("%d 到没路径 %d \n",v,i);
							}
							else
							{
								printf("%d到城市%d的最短距离为%d:\n",v,i,G->arcs[v][i]);
							    c=i;
								printf("途中经过的城市有: ");
								j=0;
								while( c!=v )
								{			   
									q[j]=c;
									c=p1[c];		   
									j++;
								}
								printf("%d",c);
								for(g=j-1;g>=0;g--)
									printf("-> %d  ",q[g]);
								
								printf("\n");
							}
							}
						}		
			}
void Dijkstra2(MGraph *G,int v,int n)
{

				if(v>n || v==0)  
				{
					printf("输入不正确\n");
					return ;
				}
				for(i=1;i<=n;i++)
				{
					p1[i]=v;
				}
				for(c=1;c<=n;c++)
					for(i=1;i<=n;i++)
						if(G->arcs[v][i]>G->arcs[v][c]+G->arcs[c][i])
						{
							G->arcs[v][i]=G->arcs[v][c]+G->arcs[c][i];
							p1[i]=c;
						}
						for(i=1;i<=n;i++)
						{
							if(v!=i)
							{
							if(G->arcs[v][i]==Maxint) 
							{
								printf("%d 到没最短时间，无法大到达%d \n",v,i);
							}
							else
							{
								printf("%d到城市%d的最短时间为%d:\n",v,i,G->arcs[v][i]);
							    c=i;
								printf("途中经过的城市有: ");
								j=0;
								while( c!=v )
								{			   
									q[j]=c;
									c=p1[c];		   
									j++;
								}
								printf("%d",c);
								for(g=j-1;g>=0;g--)
									printf("-> %d  ",q[g]);
								
								printf("\n");
							}
							}
						}		
			}






void Floyd1(MGraph *G,int n)
{
int i,j,k;
for(i=1;i<=n;i++)//设置路径长度D和路径path初植
for(j=1;j<=n;j++)
{
if(G->arcs[i][j]!=Maxint)
P[i][j]=j;//j是i的后继
else
P[i][j]=0;
D[i][j]=G->arcs[i][j];
}
for(k=1;i<=n;k++)
{//做K次迭带，每次均试图将顶点K扩充到当前求的的从I到J的最短路径
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(D[i][k]+D[k][j]<D[i][j])
{D[i][j]=D[i][k]+D[k][j];
P[i][j]=P[i][k];}

}
}
}






void Floyd2(MGraph *G,int n)
{
int i,j,k;
for(i=1;i<=n;i++)//设置路径长度D和路径path初植
for(j=1;j<=n;j++)
{
if(G->arcs[i][j]!=Maxint)
P[i][j]=j;//j是i的后继
else
P[i][j]=0;
D[i][j]=G->arcs[i][j];
}
for(k=1;i<=n;k++)
{//做K次迭带，每次均试图将顶点K扩充到当前求的的从I到J的最短路径
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(D[i][k]+D[k][j]<D[i][j])
{D[i][j]=D[i][k]+D[k][j];
P[i][j]=P[i][k];}
}
}
}








void main()
{ 
	int e;
	MGraph *G;
	int n,v,w,k;
	int a=1;
	G=(MGraph *)malloc(sizeof(MGraph));
	
	printf("输入图中顶点个数和边数n,e:");
	scanf("%d %d",&n,&e);
	CreateMGraph(G,n,e);
	while (a!=0){
		printf("\n");
		printf("---------求城市之间的最短路径----------\n");
		printf("****************************************\n");
		printf("请选择:\n");
		printf("1.求任意两个城市之间的最短路径\n");
		printf("2.求一个城市到所有城市的最短路径\n");
		printf("3.求任意两个城市之间的最短时间\n");
		printf("4.求一个城市到所有城市的最短时间\n");
		printf("0退出\n");
		printf("*****************************************\n");
		scanf("%d",&a);
		if(a==1)
		{
			
			Floyd1(G,n);
			printf("输入起点和终点：v,w:");
			scanf("%d %d",&v,&w);
			
			k=P[v][w];
			if(k==0)
				printf("顶点%d到%d无路径!",v,w);
			else
			{
				printf("从顶点%d到%d的最短路径是：%d",v,w,v);
				while(k!=w){
					printf("->%d",k);
					k=P[k][w];
			}
            printf("->%d",k);
			printf("  路径长度:%d\n",D[v][w]);
			}
		}
		else 
			if(a==2){
				printf("求单源路径，输入源点v");
				scanf("%d",&v);
				Dijkstra1(G,v,n);
			}
			if(a==3)
		{
			
			Floyd2(G,n);
			printf("输入起点和终点：v,w:");
			scanf("%d %d",&v,&w);
			
			k=P[v][w];
			if(k==0)
				printf("顶点%d到%d无时间，无法到达!",v,w);
			else
			{
				printf("从顶点%d到%d的最短时间是：%d",v,w,v);
				while(k!=w){
					printf("->%d",k);
					k=P[k][w];
			}
            printf("->%d",k);
			printf("  时间为:%d\n",D[v][w]);
			}
		}
		else 
			if(a==4){
				printf("求单源路径，输入源点v");
				scanf("%d",&v);
				Dijkstra2(G,v,n);
			}
	}
	printf("\n");
}