歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

C++實現Dijkstra算法完整代碼

標題:C++實現Dijkstra算法完整代碼

關鍵詞:Dijkstra算法代碼,Dijkstra算法,Dijkstra算法實現

#include <iostream>
#include <limits>
using 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;
  }
}

Copyright © Linux教程網 All Rights Reserved