#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define MAX 32767
#define MAXVEX  100

struct vertex
{
	int num;
	char data;   /*頂點以字符表示*/
};

typedef struct graph
{
	struct vertex vexs[MAXVEX];
	int edges[MAXVEX][MAXVEX];
}adjmax;

int dist[MAXVEX],shortest[MAXVEX][MAXVEX];
adjmax adj;
int n,e;

//建立有向圖
void creatgraph()
{
	int i,j,k,w;
	char b,t;
	printf("\n輸入頂點數：");
	scanf("%d",&n);
	printf("\n輸入邊數(e)：");
	scanf("%d",&e);
	printf("輸入頂點信息（以一個字符表示）：");
	for(i=1;i<=n;i++)
	{
		getchar();
		printf("輸入第%d個頂點的信息：",i);
		scanf("%c",&adj.vexs[i].data);
		adj.vexs[i].num=i;
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			adj.edges[i][j]=MAX;
	for(i=1;i<=n;i++)
		adj.edges[i][i]=0;
	printf("\n*****************輸入邊信息：******************\n");
	for(k=1;k<=e;k++)
	{
		getchar();
		printf("輸入第%d條邊的信息（起點，終點，權值）",k);
		scanf("%c,%c,%d",&b,&t,&w);
		i=1;
		while(i<=n && adj.vexs[i].data!=b) i++;
		if(i>n) 
		{
			printf("輸入的起點不存在!\n");
		}

	
	   j=1;
	   while(j<=n && adj.vexs[j].data!=t) j++;
	   if(j>n)
	   {
		 printf("輸入的終點不存在！\n");
	   }
	  if(i<=n && j<=n)
	   adj.edges[i][j]=w;
	  else k--;
	}
}



void print()		//打印
{
	int i,j,k;
	i=1;
	while(i<=n)
	{
		printf("\n第%d個頂點",adj.vexs[i].num);
		printf("%c\n",adj.vexs[i].data);
		i=i+1;
	}
	for(k=1;k<=n;k++)
		for(j=1;j<=n;j++)
		{
			if(adj.edges[k][j]!=32767)
				printf("\n起點:%d,終點%d,權值%d\n",k,j,adj.edges[k][j]);
		}
}

void shortpath_floyd()//求最短路徑的弗洛伊德
{
	int path[MAXVEX][MAXVEX];
	int i,j,k;
	for (i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			shortest[i][j]=adj.edges[i][j];
			path[i][j]=0;
		}
	for (k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(shortest[i][j]>(shortest[i][k]+shortest[k][j]))
				{
					shortest[i][j]=shortest[i][k]+shortest[k][j];
				    path[i][j]=k;
				}
     printf("\nFloyd算法運行成功！\n");
}



void printpath_Floyd()//打印最短路徑
{
	int i,j;
	printf("\n源點到各點之間的最短路徑\n");
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(i!=j)
			{
				if(shortest[i][j]!=MAX)
				
					printf("%c-->%c:%d\t   ",adj.vexs[i].data,adj.vexs[j].data,shortest[i][j]);
				
				else  
					printf("%c-->%c:NO WAY!\t  ",adj.vexs[i].data,adj.vexs[j].data);
			}
		}
	}
}



void shortpath_dijkstra(int v0)   //Dijkstra算法
{
	int s[MAXVEX];
	int mindis,dis,i,j,u;
	for(i=1;i<=n;i++)
	{
		dist[i]=MAX;
		dist[i]=adj.edges[v0][i];
		s[i]=0;
	}
	s[v0]=1;
	for(i=1;i<=n;i++)
	{
		mindis=MAX;
		for(j=1;j<=n;j++)
			if(s[j]==0 && dist[j]<mindis)
			{
				u=j;
				mindis=dist[j];
			}
			s[u]=1;
			for(j=1;j<=n;j++)
				if(s[j]==0)
				{
					dis=dist[u]+adj.edges[u][j];
					dist[j]=(dist[j]<dis)?dist[j]:dis;
				}	
		}
	printf("\nDijkstra算法運行成功！\n");
}


void printpath_dijkstra(v0)//打印最短路徑
{
	int i;
	printf("\n從源點%c到其它各點的最短路徑：\n",adj.vexs[v0].data);
	for(i=1;i<=n;i++)
	{
		printf("%c-->%c:",adj.vexs[v0].data,adj.vexs[i].data);
		if (dist[i]==MAX)
			printf("NO WAY\n");
		else 
			printf("%5d\n",dist[i]);
	}
}



void main()//主程序
{

	int f=1;
	int cycle=1;
	char c;
	while(cycle){	
		printf("\n 功能選擇：\n");
		printf("\n1.創建圖 ");
		printf("\n2.打印圖 ");
		printf("\n3.求最短路徑FLOYD ");
		printf("\n4.打印短路徑FLOYD ");
		printf("\n5.求短路徑DIJKSTRRA  ");
		printf("\n6.打印短路徑DIJKSTRRA  ");
		printf("\n7.退出");
		printf("\n\n請選擇");
		scanf("%c",&c);
		if(c!='7')
		{
			switch(c){
			case'1':creatgraph();break;
			case'2':print();break;
			case'3':shortpath_floyd();break;
			case'4':printpath_Floyd();break;
			case'5':printf("\n請輸入起點序號\n");
				scanf("%d",&f);
				shortpath_dijkstra(f);
				break;
			case'6':printpath_dijkstra(f);break;
			default:
				break;
			}
		}
		else cycle=0;
	}
	
}