#define INFINITY  100     /* 最大值∞ */
    /* 根据图的权值类型，分别定义为最大整数或实数 */
#define MAX_VEX  30     /*  最大顶点数目 */
#include<stdio.h>
typedef enum {DG, AG, WDG,WAG} GraphKind ;
typedef struct
{ 
	GraphKind  kind ;    /*  图的种类标志   */
	int  vexnum , arcnum ;   /*  图的当前顶点数和弧数  */
	char   vexs[MAX_VEX] ;  /*  顶点向量  */
	float   adj[MAX_VEX][MAX_VEX];
}AdjGraph ;    /*  图的结构定义   */
typedef enum boolean{False=0,True=1}BOOLEAN;

BOOLEAN  final[MAX_VEX];
int  pre[MAX_VEX] ;
float dist[MAX_VEX] ;
AdjGraph  *Create_Graph(AdjGraph * G)
{   char ch;
	int i,j;
	//printf("请输入图的种类标志：") ;
//	scanf("%d", &G->kind) ;
	G->vexnum=0 ;       /*  初始化顶点个数  */
	//ch=getchar();
	printf("请输入图中节点的标识并以#结束:\n");
	do{
		ch=getchar();
		if(ch=='#')break;
		G->vexs[G->vexnum++]=ch;
	}while(1);
	printf("请输入图的邻接矩阵(无穷大用“%d”代替):\n",INFINITY);
	for(i=0;i<G->vexnum;i++)
	printf("    %c",G->vexs[i]);
	putchar('\n');
	for(i=0;i<G->vexnum;i++)
	{
		putchar('\n');
		printf("%c   ",G->vexs[i]);
		for(j=0;j<G->vexnum;j++)
			scanf("%f",&G->adj[i][j] );
	}
	printf("你输入图的邻接矩阵为:\n");
	printf("      ");
	for(i=0;i<G->vexnum;i++)
	printf("%c      ",G->vexs[i]);
	for(i=0;i<G->vexnum;i++)
	{
		putchar('\n');
		printf("%c   ",G->vexs[i]);
		for(j=0;j<G->vexnum;j++)
			printf("%-7.2f",G->adj[i][j] );
	}
	putchar('\n');
	return(G) ; 
}

void Dijkstra_path (AdjGraph *G, int v)
           /*   从图G中的顶点v出发到其余各顶点的最短路径    */
{  
	int i,j, k, m; 
	float  min;
	for ( j=0; j<G->vexnum; j++)
	{   
		pre[j]=v ;
		final[j]=False;
		dist[j]=G->adj[v][j] ;
	}    /*  各数组的初始化  */
	dist[v]=0 ; final[v]=True ;      /*  设置S={v}  */
	for ( i=0; i<G->vexnum-1; i++) /*  其余n-1个顶点  */
	{  
		m=0 ;
		while (final[m]){m++;}   /*  找不在S中的第一个顶点m */
		min=INFINITY; 
		for ( k=0; k<G->vexnum; k++)
			{  if((final[k]==0)&&(dist[k]<min))
					{   min=dist[k];  m=k ; }
			}     /* 求出当前最小的dist[k]值  */
		printf("\nm=%d,dist[%d]=%-6.2f\n",m,m,dist[m]);
		final[m]=True ;      /*  将第k个顶点并入S中  */
		for ( j=0; j<G->vexnum; j++)
			{ if (!final[j]&&(dist[m]+G->adj[m][j]<dist[j]))
				  {   dist[j]=dist[m]+G->adj[m][j] ; 
					   pre[j]=m ;  
				  }
			 }    
	}      /* 找到最短路径  */
	
}
void Dijkstra_path_print(AdjGraph *G,int source ,int v)
{
	
	if(v==source){printf("%c",G->vexs[source]);return;}
	else
	{
		Dijkstra_path_print(G,source,pre[v]);
		printf("—>%c",G->vexs[v]);
	}

}
main()
{
	AdjGraph  G;
	char ch,temp[10];
	int i,source;
	Create_Graph(&G);
	gets(temp);
	printf("下面求多源最短路径：\n");

	for(source=0;source<G.vexnum;source++)
	{
		Dijkstra_path (&G,source);
		for(i=0;i<G.vexnum;i++)
		{
			
			if(G.vexs[i]==G.vexs[source])continue;
			else if(dist[i]>=INFINITY)
			{
				printf("\n不存在源点%c到节点%c的路径.\n",G.vexs[source],G.vexs[i]);
				continue;
			}
			printf("\n源点%c到节点%c的最短路径为：\n",G.vexs[source],G.vexs[i]);
			Dijkstra_path_print(&G,source,i);
			printf("\n源点%c到节点%c的最短路径长为：%-6.2f.\n",G.vexs[source],G.vexs[i],dist[i]);
		}
	}

}