C实现Dijkstra算法完整代码.doc

《C实现Dijkstra算法完整代码.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、C++实现Dijkstra算法完整代码标题：C++实现Dijkstra算法完整代码关键词：Dijkstra算法代码,Dijkstra算法,Dijkstra算法实现#include#includeusingnamespacestd;structNode{//定义表结点 intadjvex;//该边所指向的顶点的位置 intweight;//边的权值 Node*next;//下一条边的指针};structHeadNode{//定义头结点  intnodeName;//顶点信

2、息  intinDegree;//入度  intd;//表示当前情况下起始顶点至该顶点的最短路径,初始化为无穷大  boolisKnown;//表示起始顶点至该顶点的最短路径是否已知,true表示已知，false表示未知  intparent;//表示最短路径的上一个顶点  Node*link;//指向第一条依附该顶点的边的指针};//G表示指向头结点数组的第一个结点的指针//nodeNum表示结点个数//arcNum表示边的个数voidcreateGraph(HeadNode*G,intnodeNum,

3、intarcNum){ cout<<"开始创建图("<

4、cin>>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;i

5、eNum;i++){  cout<<"结点v"<adjvex].nodeName<<"(权:"<weight<<")"<<" ";   node=node->next;  }  cout<end权重intg

6、etWeight(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;i

7、{  G[i].d=INT_MAX;//到每一个顶点的距离初始化为无穷大  G[i].isKnown=false;//到每一个顶点的距离为未知数 } G[start-1].d=0;//到其本身的距离为0 G[start-1].parent=-1;//表示该结点是起始结点 while(true){ //====如果所有的结点的最短距离都已知,那么就跳出循环 intk; boolok=true;//表示是否全部ok for(k=0;k

8、为false  if(!G[k].isKnown){   ok=false;   break;  }  } if(ok)return; //========================================== //====搜索未知结点中d最小的,将其变为known //====这里其实可以用最小堆来实现 inti; intminIndex=-1; for(i=0;i