//求圖的最短路徑的一個例子.用迪克斯特拉算法.
// 注意:這個題的頂點的編號是從0到MAXPOINT-1 ;
#include<iostream>
#include<vector>
using namespace std;

#define MAXPOINT  10   //最大頂點數
#define limit  32767   //設置沒有路徑的無窮大

int cost[MAXPOINT][MAXPOINT]={
 {0,10,8,7,15,23,18,35,28,19},
 {10,0,15,33,15,18,21,9,17,13},
 {8,15,0,6,8,14,10,17,20,7},
 {7,33,6,0,9,18,33,12,14,16},
 {15,15,8,9,0,3,8,12,10,13},
 {23,18,14,18,3,0,6,14,10,21},
 {18,21,10,33,8,6,0,5,12,27},
 {35,9,17,12,12,14,5,0,7,10},
 {28,17,20,14,10,10,12,7,0,2},
 {19,13,7,16,13,21,27,10,2,0}
};  //圖的各邊的權值
  
struct record{
 int allpath;   //從源點到這個點的當前最短距離（權最小）
 vector<int> zuiduanlujing; //記錄最短路徑上的點.
}; 

int flag[MAXPOINT];   //標志集.記錄一個頂點是不是加入在頂點集里.

record lujing[MAXPOINT];


//向頂點集加入指定的頂點.
void shortdjs(int x)
{
 for (int i=0; i<MAXPOINT; i++) //初始化標志集 為0
 {    //初始化各點到點x的最小距離.以及路徑.
  flag[i] = 0;
  record temp;
  temp.allpath = cost[x][i];
  if (cost[x][i] != limit)
   temp.zuiduanlujing.push_back(x);
   lujing[i] = temp;
 }

 flag[x] = 1;

 int tempdingdian;
 for (int j=0; j<MAXPOINT; j++)
 {
  record temp;
  int tempallpath = limit;
  for (int k=0; k<MAXPOINT; k++) //尋找頂點集以外的離目標點最近的點
  {
   if (flag[k] == 0 && lujing[k].allpath < tempallpath)
   {
    tempdingdian = k;
    tempallpath = lujing[k].allpath;
   }
  }
  
  flag[tempdingdian] = 1;  //上一步找到的點加入頂點集.

  for (int l=0; l<MAXPOINT; l++) //更新頂點集以外的點離目標點的距離.路徑將一起被更新
  {
   if (flag[l] == 0)
   {
    if (lujing[l].allpath > 
     lujing[tempdingdian].allpath + cost[tempdingdian][l])
    {
     lujing[l].allpath = lujing[tempdingdian].allpath +
      cost[tempdingdian][l];
     lujing[l].zuiduanlujing = lujing[tempdingdian].zuiduanlujing;
     lujing[l].zuiduanlujing.push_back(tempdingdian);
    }
   }
  }
 }
}
     
int main()
{
 int m,n;  //n為開始頂點. m為結束頂點
  cout << "以下為地點代碼：\n"  ;
  cout << "   0.學校大門   1.一號教學樓   2.試驗樓 \n   "       ;
  cout << "3.運動場     4.籃球樓       5.食堂   \n  "  ;
  cout << " 6.胡夫樓     7.讀書廣場     8.圖書館 \n  "  ;
  cout << " 9.二號教學樓                10.退出\n"      ;
 do
 {
  cout << "\n請輸入開始地點代碼(頂點編號為0到10):\n";
  cin >> n;
  if(n==10)  break;
  cout << "請輸入目標地點代碼:\n";
  cin >> m;

  shortdjs(n);

  //輸出結果
  cout << "最短路徑長度為: " << lujing[m].allpath << endl;
  cout << "經過的地點代碼為: " ;
  for (vector<int>::iterator iter= lujing[m].zuiduanlujing.begin();
     iter != lujing[m].zuiduanlujing.end(); iter++)
      cout << *iter << " -> ";
  cout << m << endl;
 } while (1);

 return 0;
}