C++实现Dijkstra算法

2023-07-24 03:08:04 75

#include #include usingnamespacestd; structNode{//定义表结点 intadjvex;//该边所指向的顶点的位置 intweight;//边的权值 Node*next;//下一条边的指针 }; structHeadNode{//定义头结点 intnodeName;//顶点信息 intinDegree;//入度 intd;//表示当前情况下起始顶点至该顶点的最短路径,初始化为无穷大 boolisKnown;//表示起始顶点至该顶点的最短路径是否已知,true表示已知，false表示未知 intparent;//表示最短路径的上一个顶点 Node*link;//指向第一条依附该顶点的边的指针 }; //G表示指向头结点数组的第一个结点的指针 //nodeNum表示结点个数 //arcNum表示边的个数 voidcreateGraph(HeadNode*G,intnodeNum,intarcNum){ cout<<"开始创建图("<>begin>>end>>weight; //创建新的结点插入链接表 Node*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;iadjvex].nodeName<<"(权:"<weight<<")"<<""; node=node->next; } cout<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;iG[i].d) minIndex=i; } } //=========================================== cout<<"当前选中的结点为:v"<<(minIndex+1)<adjvex+1; intweight=getWeight(G,begin,end); if(G[minIndex].d+weightnext; } } } //打印到end-1的最短路径 voidprintPath(HeadNode*G,intend){ if(G[end-1].parent==-1){ cout<<"v"<v"<>nodeNum>>arcNum; G=newHeadNode[nodeNum]; createGraph(G,nodeNum,arcNum); cout<<"============================="<

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

C++实现Dijkstra算法

热门推荐

随机推荐