C++实现Dijkstra算法完整代码

C++实现Dijkstra算法完整代码标题：C++实现Dijkstra算法完整代码关键词：Dijkstra算法代码,Dijkstra算法,Dijkstra算法实现#ineludeviostream>#ineludevlimits>usingnamespaeestd;structNode{〃定义表结点intadjvex;〃该边所指向的顶点的位置intweight;//边的权值Node*next;〃下一条边的指针}；structHeadNode{//定义头结点intnodeName;//顶点信息intinDegree;//入度intd;〃表示当前情况下起始顶点至该顶点的最短路径，初始化为无穷大boolisKnown;〃表示起始顶点至该顶点的最短路径是否已知,true表示已知，false表示未知intparent;〃表示最短路径的上一个顶点Node*link;〃指向第一条依附该顶点的边的指针};//G表示指向头结点数组的第一个结点的指针〃nodeNum表示结点个数//areNum表示边的个数voidcreateGraph(HeadNode*G,intnodeNum,intareNum){eoutvv"开始创建图("vvnodeNumvv","vvareNumvv")"vvendl;〃初始化头结点for(inti=0;ivnodeNum;i++){G[i].nodeName=i+1;〃位置0上面存储的是结点v1,依次类推G[i].inDegree=0;〃入度为0G[i].link=NULL;}for(intj=0;jvareNum;j++){intbegin,end,weight;eoutvv"请依次输入起始边结束边权值："；ein>>begin>>end>>weight;//创建新的结点插入链接表

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<<"结点v"<<G[i].nodeName<<"的入度为"；cout<<G[i].inDegree<<",以它为起始顶点的边为:";Node*node=G[i].link;while(node!=NULL){cout<<"v"<<G[node->adjvex].nodeName<<"(权:"<<node->weight<<")"<<II")"<<IInode=node->next;}cout<<endl;〃得到begin->end权重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){〃初始化所有结点for(inti=0;i<nodeNum;i++){G[i].d=INT_MAX;〃到每一个顶点的距离初始化为无穷大G[i].isKnown=false;//到每一个顶点的距离为未知数}G[start-1].d=0;〃到其本身的距离为0G[start-1].parent=-1;〃表示该结点是起始结点while(true){//====如果所有的结点的最短距离都已知，那么就跳出循环intk;boolok=true;〃表示是否全部okfor(k=0;k<nodeNum;k++){〃只要有一个顶点的最短路径未知,ok就设置为falseif(!G[k].isKnown){ok=false;break;}}if(ok)return;//==========================================//====搜索未知结点中d最小的，将其变为known//====这里其实可以用最小堆来实现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<<"当前选中的结点为：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;〃记录最短路径的上一个结点}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<<"请输入顶点个数，边长个数："；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<<"==================