C++實現(xiàn)Dijkstra算法完整代碼

C++實現(xiàn)Dijkstra算法完整代碼標題：C++實現(xiàn)Dijkstra算法完整代碼關(guān)鍵詞：Dijkstra算法代碼,Dijkstra算法,Dijkstra算法實現(xiàn)#ineludeviostream>#ineludevlimits>usingnamespaeestd;structNode{〃定義表結(jié)點intadjvex;〃該邊所指向的頂點的位置intweight;//邊的權(quán)值Node*next;〃下一條邊的指針}；structHeadNode{//定義頭結(jié)點intnodeName;//頂點信息intinDegree;//入度intd;〃表示當前情況下起始頂點至該頂點的最短路徑，初始化為無窮大boolisKnown;〃表示起始頂點至該頂點的最短路徑是否已知,true表示已知，false表示未知intparent;〃表示最短路徑的上一個頂點Node*link;〃指向第一條依附該頂點的邊的指針};//G表示指向頭結(jié)點數(shù)組的第一個結(jié)點的指針〃nodeNum表示結(jié)點個數(shù)//areNum表示邊的個數(shù)voidcreateGraph(HeadNode*G,intnodeNum,intareNum){eoutvv"開始創(chuàng)建圖("vvnodeNumvv","vvareNumvv")"vvendl;〃初始化頭結(jié)點for(inti=0;ivnodeNum;i++){G[i].nodeName=i+1;〃位置0上面存儲的是結(jié)點v1,依次類推G[i].inDegree=0;〃入度為0G[i].link=NULL;}for(intj=0;jvareNum;j++){intbegin,end,weight;eoutvv"請依次輸入起始邊結(jié)束邊權(quán)值："；ein>>begin>>end>>weight;//創(chuàng)建新的結(jié)點插入鏈接表

Node*node=newNode;node->adjvex=end-1;node->weight=weight;++G[end-1].inDegree;〃入度加1〃插入鏈接表的第一個位置node->next=G[begin-1]」ink;G[begin-1]」ink=node;}}voidprintGraph(HeadNode*G,intnodeNum){for(inti=0;i<nodeNum;i++){cout<<"結(jié)點v"<<G[i].nodeName<<"的入度為"；cout<<G[i].inDegree<<",以它為起始頂點的邊為:";Node*node=G[i].link;while(node!=NULL){cout<<"v"<<G[node->adjvex].nodeName<<"(權(quán):"<<node->weight<<")"<<II")"<<IInode=node->next;}cout<<endl;〃得到begin->end權(quán)重intgetWeight(HeadNode*G,intbegin,intend){Node*node=G[begin-1]」ink;while(node){if(node->adjvex==end-1){returnnode->weight;}node=node->next;}}〃從start開始，計算其到每一個頂點的最短路徑voidDijkstra(HeadNode*G,intnodeNum,intstart){〃初始化所有結(jié)點for(inti=0;i<nodeNum;i++){G[i].d=INT_MAX;〃到每一個頂點的距離初始化為無窮大G[i].isKnown=false;//到每一個頂點的距離為未知數(shù)}G[start-1].d=0;〃到其本身的距離為0G[start-1].parent=-1;〃表示該結(jié)點是起始結(jié)點while(true){//====如果所有的結(jié)點的最短距離都已知，那么就跳出循環(huán)intk;boolok=true;〃表示是否全部okfor(k=0;k<nodeNum;k++){〃只要有一個頂點的最短路徑未知,ok就設置為falseif(!G[k].isKnown){ok=false;break;}}if(ok)return;//==========================================//====搜索未知結(jié)點中d最小的，將其變?yōu)閗nown//====這里其實可以用最小堆來實現(xiàn)inti;intminlndex=-1;for(i=0;i<nodeNum;i++){if(!G[i].isKnown){if(minlndex==-1)minlndex=i;elseif(G[minlndex].d>G[i].d)minlndex=i;}}//===========================================cout<<"當前選中的結(jié)點為：v"<<(minlndex+1)<<endl;G[minlndex].isKnown=true;〃將其加入最短路徑已知的頂點集//將以minlndex為起始頂點的所有的d更新Node*node=G[minlndex].link;while(node!=NULL){intbegin=minlndex+1;intend=node->adjvex+1;intweight=getWeight(G,begin,end);if(G[minlndex].d+weight<G[end-1].d){G[end-1].d=G[minlndex].d+weight;G[end-1].parent=minlndex;〃記錄最短路徑的上一個結(jié)點}node=node->next;}}}〃打印到end-1的最短路徑voidprintPath(HeadNode*G,intend){if(G[end-1].parent==-1){cout<<"v"<<end;}elseif(end!=0){printPath(G,G[end-1].parent+1);//因為這里的parent表示的是下標，從0開始,所以要加1cout<<"->v"<<end;}}intmain(){HeadNode*G;intnodeNum,arcNum;cout<<"請輸入頂點個數(shù)，邊長個數(shù)："；cin>>nodeNum>>arcNum;G=newHeadNode[nodeNum];createGraph(G,nodeNum,arcNum);cout<<"============================="<<endl;cout<<"下面開始打印圖信息…"<<endl;printGraph(G,nodeNum);cout<<"============================="<<endl;cout<<"下面開始運行dijkstra算法..."<<endl;Dijkstra(G,nodeNum,1);cout<<"==================