C++實現Dijkstra算法

本文實例為大家分享了C++實現Dijkstra算法的具體代碼，供大家參考，具體內容如下

  #include#includeusing namespace std;        struct Node { //定義表結點   int adjvex; //該邊所指向的頂點的位置   int weight;// 邊的權值   Node *next; //下一條邊的指針  };        struct HeadNode{ // 定義頭結點    int nodeName; // 頂點信息    int inDegree; // 入度    int d; //表示當前情況下起始頂點至該頂點的最短路徑,初始化為無窮大    bool isKnown; //表示起始頂點至該頂點的最短路徑是否已知,true表示已知，false表示未知    int parent; //表示最短路徑的上一個頂點    Node *link; //指向第一條依附該頂點的邊的指針  };        //G表示指向頭結點數組的第一個結點的指針  //nodeNum表示結點個數  //arcNum表示邊的個數  void createGraph(HeadNode *G, int nodeNum, int arcNum) {   cout << "開始創建圖(" << nodeNum << ", " << arcNum << ")" << endl;   //初始化頭結點   for (int i = 0; i < nodeNum; i++) {    G[i].nodeName = i+1; //位置0上面存儲的是結點v1,依次類推    G[i].inDegree = 0; //入度為0    G[i].link = NULL;   }   for (int j = 0; j < arcNum; j++) {    int begin, end, weight;    cout << "請依次輸入 起始邊 結束邊 權值: ";    cin >> begin >> end >> weight;    // 創建新的結點插入鏈接表    Node *node = new Node;    node->adjvex = end - 1;    node->weight = weight;    ++G[end-1].inDegree; //入度加1    //插入鏈接表的第一個位置    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 << "結點v" << G[i].nodeName << "的入度為";    cout << G[i].inDegree << ", 以它為起始頂點的邊為: ";    Node *node = G[i].link;    while (node != NULL) {     cout << "v" << G[node->adjvex].nodeName << "(權:" << node->weight << ")" << " ";     node = node->next;    }    cout << endl;   }  }        //得到begin->end權重  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開始，計算其到每一個頂點的最短路徑  void Dijkstra(HeadNode *G, int nodeNum, int start) {   //初始化所有結點   for (int i = 0; i < nodeNum; i++) {    G[i].d = INT_MAX; //到每一個頂點的距離初始化為無窮大    G[i].isKnown = false; // 到每一個頂點的距離為未知數   }   G[start-1].d = 0; //到其本身的距離為0   G[start-1].parent = -1; //表示該結點是起始結點   while(true) {    //==== 如果所有的結點的最短距離都已知, 那麼就跳出循環    int k;    bool ok = true; //表示是否全部ok    for (k = 0; k < nodeNum; k++) {     //只要有一個頂點的最短路徑未知,ok就設置為false     if (!G[k].isKnown) {      ok = false;      break;     }     }    if (ok) return;    //==========================================          //==== 搜索未知結點中d最小的,將其變為known    //==== 這裡其實可以用最小堆來實現    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 << "當前選中的結點為: v" << (minIndex+1) << endl;     G[minIndex].isKnown = true; //將其加入最短路徑已知的頂點集     // 將以minIndex為起始頂點的所有的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; //記錄最短路徑的上一個結點      }      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); // 因為這裡的parent表示的是下標，從0開始，所以要加1    cout << " -> v" << end;   }  }  int main() {   HeadNode *G;   int nodeNum, arcNum;   cout << "請輸入頂點個數，邊長個數: ";   cin >> nodeNum >> arcNum;   G = new HeadNode[nodeNum];   createGraph(G, nodeNum, arcNum);         cout << "=============================" << endl;   cout << "下面開始打印圖信息..." << endl;   printGraph(G, nodeNum);          cout << "=============================" << endl;   cout << "下面開始運行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;   }  }