#include <iostream>
#include <limits>
using namespace std;
 
 
struct Node { //定義表結(jié)點(diǎn)
 int adjvex; //該邊所指向的頂點(diǎn)的位置
 int weight;// 邊的權(quán)值
 Node *next; //下一條邊的指針
};
 
 
struct HeadNode{ // 定義頭結(jié)點(diǎn)
  int nodeName; // 頂點(diǎn)信息
  int inDegree; // 入度
  int d; //表示當(dāng)前情況下起始頂點(diǎn)至該頂點(diǎn)的最短路徑,初始化為無(wú)窮大
  bool isKnown; //表示起始頂點(diǎn)至該頂點(diǎn)的最短路徑是否已知,true表示已知，false表示未知
  int parent; //表示最短路徑的上一個(gè)頂點(diǎn)
  Node *link; //指向第一條依附該頂點(diǎn)的邊的指針
};
 
 
//G表示指向頭結(jié)點(diǎn)數(shù)組的第一個(gè)結(jié)點(diǎn)的指針
//nodeNum表示結(jié)點(diǎn)個(gè)數(shù)
//arcNum表示邊的個(gè)數(shù)
void createGraph(HeadNode *G, int nodeNum, int arcNum) {
 cout << "開始創(chuàng)建圖(" << nodeNum << ", " << arcNum << ")" << endl;
 //初始化頭結(jié)點(diǎn)
 for (int i = 0; i < nodeNum; i++) {
  G[i].nodeName = i+1; //位置0上面存儲(chǔ)的是結(jié)點(diǎn)v1,依次類推
  G[i].inDegree = 0; //入度為0
  G[i].link = NULL;
 }
 for (int j = 0; j < arcNum; j++) {
  int begin, end, weight;
  cout << "請(qǐng)依次輸入 起始邊 結(jié)束邊 權(quán)值: ";
  cin >> begin >> end >> weight;
  // 創(chuàng)建新的結(jié)點(diǎn)插入鏈接表
  Node *node = new Node;
  node->adjvex = end - 1;
  node->weight = weight;
  ++G[end-1].inDegree; //入度加1
  //插入鏈接表的第一個(gè)位置
  node->next = G[begin-1].link;
  G[begin-1].link = node;
 }
}
 
 
void printGraph(HeadNode *G, int nodeNum) {
 for (int i = 0; i < nodeNum; i++) {
  cout << "結(jié)點(diǎn)v" << G[i].nodeName << "的入度為";
  cout << G[i].inDegree << ", 以它為起始頂點(diǎn)的邊為: ";
  Node *node = G[i].link;
  while (node != NULL) {
   cout << "v" << G[node->adjvex].nodeName << "(權(quán):" << node->weight << ")" << " ";
   node = node->next;
  }
  cout << endl;
 }
}
 
 
//得到begin->end權(quán)重
int getWeight(HeadNode *G, int begin, int end) {
 Node *node = G[begin-1].link;
 while (node) {
  if (node->adjvex == end - 1) {
   return node->weight;
  }
  node = node->next;
 }
}
 
 
//從start開始，計(jì)算其到每一個(gè)頂點(diǎn)的最短路徑
void Dijkstra(HeadNode *G, int nodeNum, int start) {
 //初始化所有結(jié)點(diǎn)
 for (int i = 0; i < nodeNum; i++) {
  G[i].d = INT_MAX; //到每一個(gè)頂點(diǎn)的距離初始化為無(wú)窮大
  G[i].isKnown = false; // 到每一個(gè)頂點(diǎn)的距離為未知數(shù)
 }
 G[start-1].d = 0; //到其本身的距離為0
 G[start-1].parent = -1; //表示該結(jié)點(diǎn)是起始結(jié)點(diǎn)
 while(true) {
  //==== 如果所有的結(jié)點(diǎn)的最短距離都已知, 那么就跳出循環(huán)
  int k;
  bool ok = true; //表示是否全部ok
  for (k = 0; k < nodeNum; k++) {
   //只要有一個(gè)頂點(diǎn)的最短路徑未知,ok就設(shè)置為false
   if (!G[k].isKnown) {
    ok = false;
    break;
   } 
  }
  if (ok) return;
  //==========================================
 
 
  //==== 搜索未知結(jié)點(diǎn)中d最小的,將其變?yōu)閗nown
  //==== 這里其實(shí)可以用最小堆來(lái)實(shí)現(xiàn)
  int i;
  int minIndex = -1;
  for (i = 0; i < nodeNum; i++) {
   if (!G[i].isKnown) {
    if (minIndex == -1)
     minIndex = i;
    else if (G[minIndex].d > G[i].d)
     minIndex = i;
   }
  }
  //===========================================
 
 
  cout << "當(dāng)前選中的結(jié)點(diǎn)為: v" << (minIndex+1) << endl;
   G[minIndex].isKnown = true; //將其加入最短路徑已知的頂點(diǎn)集
   // 將以minIndex為起始頂點(diǎn)的所有的d更新
   Node *node = G[minIndex].link;
   while (node != NULL) {
    int begin = minIndex + 1;
    int end = node->adjvex + 1;
    int weight = getWeight(G, begin, end);
    if (G[minIndex].d + weight < G[end-1].d) {
     G[end-1].d = G[minIndex].d + weight;
     G[end-1].parent = minIndex; //記錄最短路徑的上一個(gè)結(jié)點(diǎn)
    }
    node = node->next;
   }
 }
}
 
 
//打印到end-1的最短路徑
void printPath(HeadNode *G, int end) {
 if (G[end-1].parent == -1) {
  cout << "v" << end;
 } else if (end != 0) {
  printPath(G, G[end-1].parent + 1); // 因?yàn)檫@里的parent表示的是下標(biāo)，從0開始，所以要加1
  cout << " -> v" << end;
 }
}
int main() {
 HeadNode *G;
 int nodeNum, arcNum;
 cout << "請(qǐng)輸入頂點(diǎn)個(gè)數(shù)，邊長(zhǎng)個(gè)數(shù): ";
 cin >> nodeNum >> arcNum;
 G = new HeadNode[nodeNum];
 createGraph(G, nodeNum, arcNum);
 
 
 cout << "=============================" << endl;
 cout << "下面開始打印圖信息..." << endl;
 printGraph(G, nodeNum); 
 
 
 cout << "=============================" << endl;
 cout << "下面開始運(yùn)行dijkstra算法..." << endl;
 Dijkstra(G, nodeNum, 1);
 
 
 cout << "=============================" << endl;
 cout << "打印從v1開始所有的最短路徑" << endl;
 for (int k = 2; k <= nodeNum; k++) {
  cout << "v1到v" << k << "的最短路徑為" << G[k-1].d << ": ";
  printPath(G, k);
  cout << endl;
 }
}