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

C++实现Dijkstra算法完整代码1C++实现Dijkstra算法完整代码标题：C++实现Dijkstra算法完整代码关键词：Dijkstra算法代码,Dijkstra算法,Dijkstra算法实现#includeiostream#includelimitsusingnamespacestd;structNode{//定义表结点intadjvex;//该边所指向的顶点的位置intweight;//边的权值Node*next;//下一条边的指针};structHeadNode{//定义头结点intnodeName;//顶点信息intinDegree;//入度intd;//表示当前情况下起始顶点至该顶点的最短路径,初始化为无穷大boolisKnown;//表示起始顶点至该顶点的最短路径是否已知,true表示已知，false表示未知intparent;//表示最短路径的上一个顶点Node*link;//指向第一条依附该顶点的边的指针};//G表示指向头结点数组的第一个结点的指针//nodeNum表示结点个数//arcNum表示边的个数voidcreateGraph(HeadNode*G,intnodeNum,intarcNum){cout开始创建图(nodeNum,arcNum)endl;//初始化头结点for(inti=0;inodeNum;i++){G[i].nodeName=i+1;//位置0上面存储的是结点v1,依次类推G[i].inDegree=0;//入度为0G[i].link=NULL;}for(intj=0;jarcNum;j++){intbegin,end,weight;cout请依次输入起始边结束边权值:;cinbeginendweight;//创建新的结点插入链接表C++实现Dijkstra算法完整代码2Node*node=newNode;node-adjvex=end-1;node-weight=weight;++G[end-1].inDegree;//入度加1//插入链接表的第一个位置node-next=G[begin-1].link;G[begin-1].link=node;}}voidprintGraph(HeadNode*G,intnodeNum){for(inti=0;inodeNum;i++){cout结点vG[i].nodeName的入度为;coutG[i].inDegree,以它为起始顶点的边为:;Node*node=G[i].link;while(node!=NULL){coutvG[node-adjvex].nodeName(权:node-weight);node=node-next;}coutendl;}}//得到begin-end权重intgetWeight(HeadNode*G,intbegin,intend){Node*node=G[begin-1].link;while(node){if(node-adjvex==end-1){returnnode-weight;}node=node-next;}}//从start开始，计算其到每一个顶点的最短路径voidDijkstra(HeadNode*G,intnodeNum,intstart){//初始化所有结点for(inti=0;inodeNum;i++){G[i].d=INT_MAX;//到每一个顶点的距离初始化为无穷大G[i].isKnown=false;//到每一个顶点的距离为未知数}C++实现Dijkstra算法完整代码3G[start-1].d=0;//到其本身的距离为0G[start-1].parent=-1;//表示该结点是起始结点while(true){//====如果所有的结点的最短距离都已知,那么就跳出循环intk;boolok=true;//表示是否全部okfor(k=0;knodeNum;k++){//只要有一个顶点的最短路径未知,ok就设置为falseif(!G[k].isKnown){ok=false;break;}}if(ok)return;//==========================================//====搜索未知结点中d最小的,将其变为known//====这里其实可以用最小堆来实现inti;intminIndex=-1;for(i=0;inodeNum;i++){if(!G[i].isKnown){if(minIndex==-1)minIndex=i;elseif(G[minIndex].dG[i].d)minIndex=i;}}//===========================================cout当前选中的结点为:v(minIndex+1)endl;G[minIndex].isKnown=true;//将其加入最短路径已知的顶点集//将以minIndex为起始顶点的所有的d更新Node*node=G[minIndex].link;while(node!=NULL){intbegin=minIndex+1;intend=node-adjvex+1;intweight=getWeight(G,begin,end);if(G[minIndex].d+weightG[end-1].d){G[end-1].d=G[minIndex].d+weight;G[end-1].parent=minIndex;//记录最短路径的上一个结点}C++实现Dijkstra算法完整代码4node=node-next;}}}//打印到end-1的最短路径voidprintPath(HeadNode*G,intend){if(G[end-1].parent==-1){coutvend;}elseif(end!=0){printPath(G,G[end-1].parent+1);//因为这里的parent表示的是下标，从0开始，所以要加1cout-vend;}}intmain(){HeadNode*G;intnodeNum,arcNum;cout请输入顶点个数，边长个数:;cinnodeNumarcNum;G=newHeadNode[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(intk=2;k=nodeNum;k++){coutv1到vk的最短路径为G[k-1].d:;printPath(G,k);coutendl;}}