admin 管理员组

文章数量: 1184232


2024年4月21日发(作者：regionprops python)

(完整)Dijkstra算法的流程图

开始

定义全局变量

dist[N]，

v0,cost[N][N]

初始化变量

final[N],i,v,w,

min,k

K=0

N

K

Y

V=0

N

V

Y

final[v] =

false;dist[v] =

cost[v0][v];

END

return 0;

final[v0] =

true

i=0

N

i

Y

i=0

初始最短长度无

穷大

Ni

Y

W=0

N

I++

W

Y

!final[w] &&

dist[w] < min

Y

Min =

dist[w]

v = w;

加入新边

final[v] =

true

W=0

N

W

Y

!final[w] &&

dist[v] +

cost[v][w] <

dist[w]

dist[w] =

dist[v] +

cost[v][w];

N

I++

v0++;输出dist[i]

K++;

W++

W++

Dijkstra算法的流程图

需求和规格说明：

Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径.

主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止.Dijkstra算法能

(完整)Dijkstra算法的流程图

得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低.

算法本身并不是按照我们的思维习惯——求解从原点到第一个点的最短路径,再到

第二个点的最短路径，直至最后求解完成到第n个点的最短路径，而是求解从原点

出发的各有向路径的从小到大的排列，但是算法最终确实得到了从原点到图中其余

各点的最短路径，可以说这是个副产品,对于算法的终结条件也应该以求得了原点

到图中其余各点的最短路径为宜.清楚了算法的这种巧妙构思后，理解算法本身就

不是难题了.

实现注释：

想要实现的功能：

Dijkstra算法是用来求任意两个顶点之间的最短路径。在该实验中，我们用邻接矩

阵来存储图。在该程序中设置一个二维数组来存储任意两个顶点之间的边的权值。

用户可以将任意一个图的信息通过键盘输入，让后在输入要查找的两个顶点，程序

可以自动求出这两个顶点之间的最短路径

.

已经实现的功能:

在该实验中，我们用邻接矩阵来存储图。在该程序中设置一个全局变量的二维数组,

用它来存储任意两个顶点之间的边的权值。然后通过最短路径的计算,输入从任意

两个顶点之间的最短路径的大小。

用户手册：

对于改程序，不需要客户进行什么复杂的输入，关键是用来存放图的任意两个顶点

之间的边的权值的二维数组的初始化,即将要通过Dijkstra算法求最短路径的图各

条边的权值放入二维数组中。这样程序就可以自动的计算出任意两个顶点之间的最

短路径并且进行输出.

设计思想：

s为源，w［u，v] 为点u 和v 之间的边的长度，结果保存在 dist［]


本文标签： 算法 路径 任意 顶点 计算

版权声明：本文标题：(完整)Dijkstra算法的流程图 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1713679575a646635.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。