dijkstra:号称最贪心的算法--Dijkstra算法

 2021-07-16 1:08    77  

Dijkstra算法算是贪心思想实现的,首先把起点到所有点的距离存下来找个最短的,然后松弛一次再找出最短的,所谓的松弛操作就是,遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近,如果更近了就更新距离,这样把所有的点找遍之后就存下了起点到其他所有点的最短距离dijkstra。问题引入:指定一个点(源点)到其余各个顶点的最短路径,也叫做“单源最短路径”。例如求下图中的1号顶点到2、3、4、5、6号顶点的最短路径。

dijkstra:号称最贪心的算法--Dijkstra算法

dijkstra:号称最贪心的算法--Dijkstra算法

dijkstra:号称最贪心的算法--Dijkstra算法

dijkstra:号称最贪心的算法--Dijkstra算法

dijkstra:号称最贪心的算法--Dijkstra算法

dijkstra:号称最贪心的算法--Dijkstra算法

dijkstra:号称最贪心的算法--Dijkstra算法

dijkstra:号称最贪心的算法--Dijkstra算法

dijkstra:号称最贪心的算法--Dijkstra算法

下面我们来模拟一下dijkstra:

dijkstra:号称最贪心的算法--Dijkstra算法

dijkstra:号称最贪心的算法--Dijkstra算法

dijkstra:号称最贪心的算法--Dijkstra算法

Dijkstra算法具体步骤为:(1)初始时dijkstra,S只包含源点,即S=,v的距离为0。U包含除v外的其他顶点,U中顶点u距离为边上的权(若v与u有边)或 )(若u不是v的出边邻接点)。

dijkstra:号称最贪心的算法--Dijkstra算法

(2)从U中选取一个距离v最小的顶点k,把k,加入S中(该选定的距离就是v到k的最短路径长度)。

(3)以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u(u U)的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边上的权。

(4)重复步骤(2)和(3)直到所有顶点都包含在S中。

接下来是代码:已经把几个过程都封装成了基本模块:

本文标签:算法

原文链接:https://www.xgfox.com/alpx/949.html

本文版权:如无特别标注,本站文章均为原创。