C++Dijkstra 알고리즘 구현

본 논문 의 사례 는 C+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;
 }
}

이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.