#include < iostream.h >
#include < limits.h >

#define	ERROR 0
#define OK 1
#define FALSE 0
#define TRUE 1
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM  30


typedef unsigned int VRType;
typedef char VertexType;
typedef char VertexInfo;
typedef int Status ;
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct ArcCell
{
   VRType weight;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct VexNode
{
	VertexType data;
	VertexInfo* maininfo;
	VertexInfo* info;
}VexNode, VexArray[MAX_VERTEX_NUM];

typedef struct
{
  VexArray Vexs;   
  AdjMatrix  arcs;
  int vexnum, arcnum;
}MGraph;

typedef  int ShortPathTable[MAX_VERTEX_NUM];

int LocateVex( MGraph G, VertexType v1 )
{
	for ( int i = 0; i < G.vexnum; i++ )
		if ( G.Vexs[i].data == v1 )
			return i;

	return ERROR;
}

Status CreateGraph( MGraph & G )
{
  G.vexnum = 10;
  G.arcnum = 18;
  char * ch = "abcdefghij";

  for ( int i = 0; i < G.vexnum; i++ )
  {
    G.Vexs[i].data = ch[i];
  }
  G.Vexs[0].maininfo = "科技樓";
  G.Vexs[1].maininfo = "中心廣場";
  G.Vexs[2].maininfo = "圖書館";
  G.Vexs[3].maininfo = "教學樓"; 
  G.Vexs[4].maininfo = "實驗樓";
  G.Vexs[5].maininfo = "B樓";
  G.Vexs[6].maininfo = "行政樓";
  G.Vexs[7].maininfo = "A樓";
  G.Vexs[8].maininfo = "蝴蝶湖";
  G.Vexs[9].maininfo = "校門口";

  G.Vexs[0].info = " 科技樓，功能:由實驗室，機房，課室組成。主要用來上課，供學生做物理實驗和進行上機操作。";
  G.Vexs[1].info = " 中心廣場，功能：主要用來開大型會議或舉行文藝活動，例如十大歌手，國慶晚會等";
  G.Vexs[2].info = " 圖書館，功能：有五層，一樓主要用于展覽，二樓用于租借書籍，三樓主要用于藏書,四樓有大量雜志，五樓是圖書館工作人員辦公室。每層的教室還能供同學們自修使用。";
  G.Vexs[3].info = " 教學樓，功能：主要由課室，電教室和多媒體教室組成，是學校上課的主要地方。";
  G.Vexs[4].info = " 實驗樓，功能：由實驗室，養殖室和溫室組成，是水院和農院同學做實驗的主要地方。";
  G.Vexs[5].info = " B樓，功能：由課室組成，用于上課。";
  G.Vexs[6].info = " 行政樓，功能：是學校領導辦公的主要地方。";
  G.Vexs[7].info = " A樓，功能：由教室和語音室組成，主要用于外語學院上課和聽力課。";
  G.Vexs[8].info = " 蝴蝶湖，功能：學校的景點之一，是學生們聊天，飯后散步的好地方。";
  G.Vexs[9].info = " 校門口，功能：由此進入校園。";

  for ( i = 0; i < G.vexnum; i++ )
	for ( int j = 0; j < G.vexnum; j++ )
      G.arcs[i][j].weight = INFINITY;

  G.arcs[0][1].weight = 3;
  G.arcs[0][2].weight = 6;
  G.arcs[0][9].weight = 25;
  G.arcs[1][2].weight = 2;
  G.arcs[1][3].weight = 4;
  G.arcs[1][0].weight = 3;
  G.arcs[2][0].weight = 6;
  G.arcs[2][1].weight = 2;
  G.arcs[2][3].weight = 4;
  G.arcs[2][5].weight = 8;
  G.arcs[3][1].weight = 4;
  G.arcs[3][2].weight = 4;
  G.arcs[3][4].weight = 3;
  G.arcs[3][6].weight = 10;
  G.arcs[4][3].weight = 3;
  G.arcs[4][5].weight = 3;
  G.arcs[4][6].weight = 6;
  G.arcs[5][2].weight = 8;
  G.arcs[5][4].weight = 3;
  G.arcs[5][6].weight = 5;
  G.arcs[5][7].weight = 3;
  G.arcs[6][3].weight = 10;
  G.arcs[6][4].weight = 6; 
  G.arcs[6][5].weight = 5; 
  G.arcs[6][7].weight = 4;
  G.arcs[6][8].weight = 4;
  G.arcs[6][9].weight = 8;
  G.arcs[7][5].weight = 3;
  G.arcs[7][6].weight = 4;
  G.arcs[7][8].weight = 3;
  G.arcs[8][6].weight =	4;
  G.arcs[8][7].weight = 3;
  G.arcs[8][9].weight = 3; 
  G.arcs[9][8].weight = 3;
  G.arcs[9][6].weight = 8; 
  G.arcs[9][0].weight = 25;
	  
  return OK;
}

void ShortesPath_DIJ( MGraph G, char v0, PathMatrix &P, ShortPathTable &D )
//用Dijdstra算法求有向網G的V0頂點到其余頂點v的最短路徑P[v][w]及其帶權長度D[v].
//若P[v][w]為TRUE，則w是從v0到v當前求得最短路徑上的頂點
//final[v]為TRUE當且僅當v<s,即已經求得從v0到v的最短路徑
{
  int r;
  int min;
  int Final[MAX_VERTEX_NUM];
  int i = LocateVex( G, v0 );

  for ( int j = 0; j < G.vexnum; j++ )// 初始化D[j]、P[j][k]、Final[j]
  {
    Final[j] = FALSE;
	D[j] = G.arcs[i][j].weight;

	for ( int k = 0; k < G.vexnum; k++ )
	  P[j][k] = FALSE;

	  if ( D[j] < INFINITY )
	  {
		P[j][i] =TRUE;
		P[j][j] = TRUE;
	  }
  }
  
  D[i] = 0;
  Final[i] = TRUE;//初始化，v0頂點屬于S集

  //開始主循環,每次求得v0到某個v頂點的最短路徑,并加v到s集 
  for (  j = 1; j < G.vexnum; j++ )//其余G.vexnum-1個頂點
  {
	min = INFINITY;//目前所知離v0頂點的最近距離
    for ( int  k = 0; k < G.vexnum; k++ )//計算離v0頂點最近的頂點r
	  if ( !Final[k] )//w 頂點 在V-S中
		if( D[k] < min )
		{
		  r = k;
		  min = D[k];
		}

	Final[r] = TRUE;//離v0頂點最近的r加入S中
	 
	for (  k = 0; k < G.vexnum; k++ )//表示v0--r--其它頂點k權值與v0直接到其它頂點k權值比較,其它頂點在V-S集中
	{  
	  if ( !Final[k] && ( (min + G.arcs[r][k].weight) < D[k] ))
	  {
		D[k] = min + G.arcs[r][k].weight;//D[k]表示從i到k的最短權值

		for ( int n = 0; n < G.vexnum; n++ )
		  P[k][n] = P[r][n];

		  P[k][k] = TRUE;
	  }//if
	}//for
  }	//for
}//ShortesPath_DIJ

void ShowPath( MGraph G, char v0, char v1, PathMatrix P, ShortPathTable D )
{
  int min, r, k, e, i,count;
  count = 0;                 //計算經過多少個頂點
  int a[10];                 //存放經過頂點的下標  
  k = LocateVex( G, v0);
  e = LocateVex( G, v1);
	
  for ( int j = 0; j < G.vexnum; j++ )//初始化
    a[j] = INFINITY;

  for ( i = 0, j = 0; i < G.vexnum && j < G.vexnum; i++, j++ )
  //P若P[v][w]為TRUE，則w是從v0到v當前求得最短路徑上的頂點
  {
    if ( P[e][i] ) //k到e最短路徑經過i,保存i到a[j]     
	{
	  a[j] = i;count++;
	}
  }
  if ( count == 2 )
  {
	cout<<G.Vexs[k].maininfo<<"到"<<G.Vexs[e].maininfo<<"是直接到達的"<<endl;
	cout<<"它的長度是 "<<D[e]<<endl;//D[e]保存了k到e點的最短長度
	return ;
  }
	
  cout<<"從"<<G.Vexs[k].maininfo<<"到"<<G.Vexs[e].maininfo<<"它經過"<<(count - 2)<<"個點，分別是"<<endl;
  
  a[k] = INFINITY;
  a[e] = INFINITY;
   
  for (  j = 0; j < count ; j++ )
  {
	min  = INFINITY;//初始化
	 
	for ( int k = 0; k < G.vexnum; k++ )
	{
	  if ( a[k] != INFINITY && min > D[a[k]] )
	  {
		min = D[a[k]];       //在經過頂點上尋找權值小的為先經過
		r = a[k];            //記住最小點的位置
	  }
	}
	if ( a[r] != INFINITY )cout<<G.Vexs[r].maininfo<<endl;
      a[r] = INFINITY;         //表示
  }
  cout<<"它的長度是 "<<D[e]<<endl;
}
			  
void main()
{

  char v0;
  char v1;
  char ch, ding;
  int n;
  int min = INFINITY;
  MGraph G;
  CreateGraph(G );
  PathMatrix P;
  ShortPathTable D;
    
  cout << " a代表科技樓 " << "b代表中心廣場 " << "c代表圖書館 " << endl;
  cout << " d代表教學樓 " << "e代表實驗樓 " << "f代表B樓 " << endl;
  cout << " g代表行政樓 " << "h代表A樓 " << "i代表蝴蝶湖 " << "j代表校門口 " << endl;
  cout <<" 如果你想查詢某個頂點的信息請按 u 鍵" << endl;
  cout <<" 如果你想查詢兩個地點的最短路徑請按 p 鍵"<< endl; 
  cin >> ch;
  do		
  {
	while ( ch == 'u' )
	{
	  cout << "請你輸入一 個頂點" << endl;
	  cin >> ding;
      n = LocateVex( G, ding );
	  cout << G.Vexs[n].info << endl << endl;
	  cout << "如果你還想繼續查詢某個頂點的信息請按 u 鍵，但如果你想查詢兩個地點" << endl;
	  cout << "的最短路徑請按 p 鍵，如果想退出請按其它鍵" << endl;
	  cin >> ch;
	}
	while ( ch == 'p' )
	{
	  cout << " a代表科技樓 " << "b代表中心廣場 " << "c代表圖書館 " << endl;
	  cout << " d代表教學樓 " << "e代表實驗樓 " << "f代表B樓 " << endl;
	  cout << " g代表行政樓 " << "h代表A樓 " << "i代表蝴蝶湖 " << "j代表校門口 " << endl;
	  cout << "請輸入兩個頂點字符" << endl;
      cin >> v0 >> v1;
      ShortesPath_DIJ( G, v0, P, D );
	  ShowPath( G, v0, v1, P, D);
      cout << endl;
	  cout << "如果你還想繼續查詢兩個地點的最短路徑請按 p 鍵, 但如果你想查詢" << endl;
	  cout << "某個頂點的信息請按 u 鍵,如果想退出請按其它鍵" << endl;
	  cin >> ch;
	}
  }while ( ch == 'u' || ch == 'p' );
    
}