Dijkstra 算法介绍

x33g5p2x  于2022-07-07 转载在 其他  
字(1.6k)|赞(0)|评价(0)|浏览(256)

一 问题背景

在现实生活中,很多问题都可以转化为图来解决问题。例如,计算地图中两点之间的最短距离、网络最小成本布线,以及工程进度控制,等等。这些问题都涉及最小路径的求解。

二 Dijkstra 算法

给定有向带权图 G=(V,E),其中每条边的权值都是非负实数。此外,给定 V 中的一个节点,称之为源点。求解从源点到其他各个节点的最短路径,路径长度指路上各边权之和。

可以使用 Dijkstra 算法对最短路径进行求解。Dijkstra 算法是解决单源最短路径的贪心算法,它先求出长度最短的一条路径,再参照该路径求出长度次短的一条路径,直到求出从源点到其他各个节点的最短路径。

Dijkstra 算法的基本思想:假定源点 u,节点集合 V 被划分为两部分:集合 S 和集合 V-S,初始时,在集合 S 中仅包含源点 u,S 中的节点到源点的最短路径已经确定。集合 V-S 所包含的节点到源点的最短路径待定,称从源点出发只经过集合 S 中的节点到达集合 V-S 中的节点的路径为特殊路径,并用数字 dist[] 记录当前每个节点所对应的最短特殊路径长度。

Dijkstra 算法采用贪心策略是选特殊路径长度最短的路径,将其连接的集合 V-S 中的节点加入集合 S,同时更新数字 dist[]。一旦集合 S 包含所有节点,dist[] 就是从源点到所有其他节点的最短路径长度。

三 算法步骤

1 数据结构

设置地图的邻接矩阵 G.Egge[][],即如果从源点 u 到节点 i 有边,就让 G.Egge[][], 等于<u,i>的权值,否则 G.Egge[][],=无穷大;采用一维数组dist[i] 记录从源点到节点 i 的最短路径长度;采用一维数组 p[i] 记录最短路径商节点 i 的前驱。

2 初始化

另集合 S={u},对于集合 V-S 中的所有节点 i,都初始化 dist[i] =  G.Egge[u][i],如果从源点 u 到节点 i 有边相连,则初始化 p[i] =u,否则 p[i] = -1。 

3 找最小

在集合 V-S 中查找 dist[] 最小的节点 t,即 dist[t]=min(dist[j]),其中 j 属于集合 V-S,则节点 t 就是集合 V-S 中距离源点 u 最近的节点。

4 加入集合 S 中

将节点 t 加入集合 S 中,同时更新集合 V-S。

5 判结束

如果集合 V-S 为空,则算法结束,否则转向不足 6。

6 借东风

在步骤 3 中已经找到了从源点到节点 t 的最短路径,那么对集合 V -S 中节点 t 的所有邻接点 j,都可以借助 t 走捷径。如果 dist[j] > dist[t] +  G.Egge[t][j],则 dist[j] = dist[t] +  G.Egge[t][j],记录节点 j 的前驱为 t,有p[j] = t,转向步骤3。

由此,可求得从源点 u 到图的其余各个节点的最短路径及长度,也可以通过数组 p[] 逆向找到最短路径上的节点。

四 图解

有一个景点的地图,如下图所示,假设从节点 1 出发,求到其他各个节点的最短路径。

1 数据结构

2 初始化

3 在集合 V-S ={2,3,4,5}中查找 dist[] 最小的节点 t,找到的最小值为 2,对应的节点 t=2,如下图所示。

4 加入集合 S。将节点 2 加入集合S={1,2}中,同时更新集合V-S={3,4,5},如下图所示。

5 刚找到节点2,通过该点,更新 dist[] 和 p[]

6 在集合 V-S={3,4,5}中,查找 dist[] 最小的节点 t,找到最小值为 4,对应的节点 t=3。

7 将节点 3 加入集合 S={1,2,3}中,同时更新 V-S={4,5},如下图所示。

8 刚找到节点3,通过该点,更新 dist[] 和 p[]

9 V-S={4,5}中,查找 dist[] 最小的节点 t,找到最小值为 5,对应的节点 t=5。

10 将节点 5 加入集合 S={1,2,3,5}中,同时更新 V-S={4},如下图所示。

11 刚找到节点5,通过该点,更新 dist[] 和 p[],因为节点 5 没有邻接点,所以不更新。

12 V-S={4}中,查找 dist[] 最小的节点 t,找到最小值为 8,对应的节点 t=4。

13 将节点 4 加入集合 S={1,2,3,5,4}中,同时更新 V-S={},如下图所示。

14 在集合 V-S={] 为空时算法结束。

相关文章