c实现dijkstra算法完整代码159.pdf
C+实现 Dijkstra 算法完好代码 标题：C+实现 Dijkstra 算法完好代码 关键词：Dijkstra 算法代码,Dijkstra 算法,Dijkstra 算法实现#include#include using namespace std;struct Node /定义表结点 int adjvex;/该边所指向的顶点的位置 int weight;/边的权值 Node*next;/下一条边的指针;struct HeadNode/定义头结点 int nodeName;/顶点信息 int inDegree;/入度 int d;/表示当前情况下起始顶点至该顶点的最短途径,初始化为无穷大 bool isKnown;/表示起始顶点至该顶点的最短途径是否,true 表示，false 表示未知 int parent;/表示最短途径的上一个顶点 Node*link;/指向第一条依附该顶点的边的指针;/G 表示指向头结点数组的第一个结点的指针/nodeNum 表示结点个数/arcNum 表示边的个数 void createGraph(HeadNode*G,int nodeNum,int arcNum)cout 开始创立图(nodeNum ,arcNum )endl;/初始化头结点 for(int i=0;i nodeNum;i+)Gi.nodeName=i+1;/位置 0 上面存储的是结点 v1,依次类推 Gi.inDegree=0;/入度为 0 Gi.link=NULL;for(int j=0;j arcNum;j+)int begin,end,weight;cout begin end weight;/创立新的结点插入链接表 Node*node=new Node;node-adjvex=end-1;node-weight=weight;+Gend-1.inDegree;/入度加 1 /插入链接表的第一个位置 node-next=Gbegin-1.link;Gbegin-1.link=node;void printGraph(HeadNode*G,int nodeNum)for(int i=0;i nodeNum;i+)cout 结点 v Gi.nodeName 的入度为;cout Gi.inDegree ,以它为起始顶点的边为:;Node*node=Gi.link;while(node!=NULL)cout v adjvex.nodeName (权:weight )next;cout end 权重 int getWeight(HeadNode*G,int begin,int end)Node*node=Gbegin-1.link;while(node)if(node-adjvex=end-1)return node-weight;node=node-next;/从 start 开始，计算其到每一个顶点的最短途径 void Dijkstra(HeadNode*G,int nodeNum,int start)/初始化所有结点 for(int i=0;i nodeNum;i+)Gi.d=INT_MAX;/到每一个顶点的间隔 初始化为无穷大 Gi.isKnown=false;/到每一个顶点的间隔 为未知数 Gstart-1.d=0;/到其本身的间隔 为 0 Gstart-1.parent=-1;/表示该结点是起始结点 while(true)/=假设所有的结点的最短间隔 都,那么就跳出循环 int k;bool ok=true;/表示是否全部 ok for(k=0;k nodeNum;k+)/只要有一个顶点的最短途径未知,ok 就设置为 false if(!Gk.isKnown)ok=false;break;if(ok)return;/=/=搜索未知结点中 d 最小的,将其变为 known /=这里其实可以用最小堆来实现 int i;int minIndex=-1;for(i=0;i Gi.d)minIndex=i;/=cout 当前选中的结点为:v (minIndex+1)adjvex+1;int weight=getWeight(G,begin,end);if(GminIndex.d+weight next;/打印到 end-1 的最短途径 void printPath(HeadNode*G,int end)if(Gend-1.parent=-1)cout v end;else if(end!=0)printPath(G,Gend-1.parent+1);/因为这里的 parent 表示的是下标，从 0 开始，所以要加 1 cout v end;int main()HeadNode*G;int nodeNum,arcNum;cout nodeNum arcNum;G=new HeadNodenodeNum;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(int k=2;k=nodeNum;k+)cout v1 到 v k 的最短途径为 Gk-1.d :;printPath(G,k);cout endl;
