《Dijkstra算法的流程图oiz》由会员分享，可在线阅读，更多相关《Dijkstra算法的流程图oiz（8页珍藏版）》请在金锄头文库上搜索。
1、 Dijkkstrra算法法的流程程图需求和规规格说明明：Dijkkstrra算法法是典型型最短路路算法，用用于计算算一个节节点到其其他所有有节点的的最短路路径。主主要特点点是以起起始点为为中心向向外层层层扩展，直直到扩展展到终点点为止。DDijkkstrra算法法能得出出最短路路径的最最优解，但但由于它它遍历计计算的节节点很多多，所以以效率低低。算法本身身并不是是按照我我们的思思维习惯惯求解解从原点点到第一一个点的的最短路路径，再再到第二二个点的的最短路路径，直直至最后后求解完完成到第第n个点点的最短短路径，而而是求解解从原点点出发的的各有向向路径的的从小到到大的排排列，但但是算法法最终确确
2、实得到到了从原原点到图图中其余余各点的的最短路路径，可可以说这这是个副副产品，对对于算法法的终结结条件也也应该以以求得了了原点到到图中其其余各点点的最短短路径为为宜。清清楚了算算法的这这种巧妙妙构思后后，理解解算法本本身就不不是难题题了。实实现注释释：想要实现现的功能能：Dijkkstrra算法法是用来来求任意意两个顶顶点之间间的最短短路径。在该实验中，我们用邻接矩阵来存储图。在该程序中设置一个二维数组来存储任意两个顶点之间的边的权值。用户可以将任意一个图的信息通过键盘输入，让后在输入要查找的两个顶点，程序可以自动求出这两个顶点之间的最短路径。已经实现现的功能能：在该实验验中，我我们用邻邻接矩
3、阵阵来存储储图。在在该程序序中设置置一个全全局变量量的二维维数组，用用它来存存储任意意两个顶顶点之间间的边的的权值。然然后通过过最短路路径的计计算，输输入从任任意两个个顶点之之间的最最短路径径的大小小。用户手册册：对于改程程序，不不需要客客户进行行什么复复杂的输输入，关关键是用用来存放放图的任任意两个个顶点之之间的边边的权值值的二维维数组的的初始化化，即将将要通过过Dijjksttra算算法求最最短路径径的图各各条边的的权值放放入二维维数组中中。这样样程序就就可以自自动的计计算出任任意两个个顶点之之间的最最短路径径并且进进行输出出。设计思想想：s为源，wwu，vv 为为点u 和v 之间的的边的
4、长长度，结结果保存存在 ddistt初始化：源的距距离diists设设为0，其其他的点点距离设设为无穷穷大，同同时把所所有的点点状态设设为没有有扩展过过。循环n-1次：1. 在在没有扩扩展过的的点中取取一距离离最小的的点u，并并将其状状态设为为已扩展展。2. 对对于每个个与u相相邻的点点v，如如果diistu + wwu，vv diistv，那那么把ddisttv更新成成更短的的距离ddisttu + wuu，v。此时时到点vv的最短短路径上上，前一一个节点点即为uu。结束：此此时对于于任意的的u，ddisttu就是ss到u的的距离。程序源代代码：#inccludde #inccludde C
5、onnio.h#deffinee trrue 1#deffinee faalsee 0#deffinee I 99999 / 无穷穷大 #deffinee N 5 / 城市顶顶点的数数目 int cosstNNNN = 0,3,II,8,I, 3,0,55,I,4, I,5,00,4,7, 8,I,44,0,2, I,4,77,2,0;int disstNN; / 存存储当前前最短路路径长度度 int v0 = A - 665; / 初初始点是是 A int maiin() intt fiinallN,i,v,ww,miin,kk;priintff(n任意意两个定定点之间间的最短短路径如如下：
6、nnn); forr(k=0;kkN;k+) / 初始始化最短短路径长长度数据据，所有有数据都都不是最最终数据据 foor (v = 0; v NN; vv+) ffinaalvv = faalsee; ddisttv = cosstvv0v; / 首先先选v00到v00的距离离一定最最短，最最终数据据 fiinallv00 = trrue; / 寻找找另外 N-11 个结结点 foor (i = 0; i NN-1; i+) mmin = II; / 初初始最短短长度无无穷大 / 寻寻找最短短的边 ffor (w = 00; ww N; w+) if (!ffinaalww & ddistt
7、w minn) miin = diistw; v = ww; ffinaalvv = trrue; / 加入新新边 ffor (w = 00; ww N; w+) / 更新新 diist 数数据 if (!ffinaalww & ddisttv + cosstvvww diistw) diistw = ddisttv + cosstvvww; foor (i = 0; i %c: %2ddt, vv0 + 655, ii + 65, diisti); prrinttf(n); v00+; retturnn 0;运行结果果：调试报告告：错误：运行结果果如下：而正确的的运行结结果是这这样的：出现的问问题是在在寻找最最短路径径和更新新 diist 数数据的两两个foor循环环之间少少了一个个赋值语语句。如如下：finaalvv = trrue; / 加入新新边当每次找找到从vv0到其其它各定定点的最最短路径径是，将将该定点点标记为为已经找找到了最最短路径径，下次次查找是是不再对对该顶点点的diist的值值进行改改变。
