Dijkstra算法的流程图

1、Dijkstra算法的流程图 Dijkstra算法的流程图 需求和规格讲明： Dijkstra算法是典型最短路算法，用于运算一个节点到其他所有节点的最短路径。要紧特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历运算的节点专门多，因此效率低。 算法本身并不是按照我们的思维适应一一求解从原点到第一个点的最短路径，再到第二个点的最短路径，直至最后求解完成到第n个点的最短 路径， 而是求解从原点动身的各有向路径的从小到大的排列， 然而算法最终确实得到了从原点到图中其余各点的最短路径， 能够讲这是个副产品， 关于算法的终结条件也应该以求得了原

2、点到图中其余各点的最短路径为宜。清晰了算法的这种巧妙构思后，明白得算法本身就不是难题了。实现注释： 想要实现的功能： Dijkstra算法是用来求任意两个顶点之间的最短路径。 在该实验中， 我们用邻接矩阵来储备图。 在该程序中设置一个二维数组来储备任意两个顶点之间的边的权值。 用户能够将任意一个图的信息通过键盘输入， 让后在输入要查找的两个顶点， 程序能够自动求出这两个顶点之间的最短路径。 差不多实现的功能： 在该实验中，我们用邻接矩阵来储备图。在该程序中设置一个全局变量的二维数组，用它来储备任意两个顶点之间的边的权值。然后通过最短路径的运算，输入从任意两个顶点之间的最短路径的大小。 用户手册

3、： 关于改程序，不需要客户进行什么复杂的输入，关键是用来存放图的任意两个顶点之间的边的权值的二维数组的初始化，立即要通过Dijkstra算 法求最短路径的图各条边的权值放入二维数组中。 如此程序就能够自动的运算出任意两个顶点之间的最短路径同时进行输出。 设计思想: s为源，wu,v为点u和v之间的边的长度，结果储存在dist 初始化：源的距离dists设为0,其他的点距离设为无穷大，同时把所有的点状态设为没有扩展过。 循环n-1次： 1 .在没有扩展过的点中取一距离最小的点u,并将其状态设为已扩展。 2 .关于每个与u相邻的点v,如果distu+wu,vdistv,那么把distv更新成更短的

4、距离distu+wu,v。现在到点v的最短路径上,前一个节点即为u。 终止：现在关于任意的u,distu确实是s到u的距离。 程序源代码： #include#includeConio.h#definetrue1#definefalse0#defineI9999 #defineN5 目 intcostNN=0,3,I,8,I,3,0,5,I,4,I,5,0,4,7,8,I,4,0,2,I,4,7,2,0; intdistN; 前最短路径长度 intv0=A-65;/初始点 是A intmain() ( intfinalN,i,v,w,min,k; printf(n任意两个定点之间白最短路径如下：

5、nn); for(k=0;kN;k+)( /无穷大 /都市顶点的数 /储备当 /初始化最短路径长度数据，所有数据都不是最终数据 for(v=0;vN;v+)(finalv=false; distv=costv0v; /第一选v0到v0的距离一定最短，最终数据finalv0=true; /查找另外N-1个结点 for(i=0;iN-1;i+)( min=I;/初始最短长度无穷大 /查找最短的边 for(w=0;wN;w+)( if(!finalw&distwmin)( min=distw; v=w; ) finalv=true;/加入新边 for(w=0;wN;w+) /更新dist数据

6、 if(!finalw&distv+costvwdistw) distw=distv+costvw; ) ) ) for(i=0;i%c:%2dt”,v0+65,i+65,disti); ) B B- -ftft： 3 R R- -R R： R R B B- -yCyC： snsn- -D=D= R R- -EE： 4 4C C- -AA: : 9 C C- -BB； 5 5 e-c： n n C C- -D:D: 4 4 C C- -E:E: C C： s s D D- -BB： & & P P- -MJMJ： 4 4 e e D D- -EE： 2 2E E- -AA： 7 7 E E- -DD： 4 4 E E- -CC： E E- -DD： 2 2 E E- -EE： 3 3ressanyto1仁口qltLiiUP. 显现的咨询题是在查找最短路径和更新dist数据的两个fo