【数据结构-图】3.图的最短路径的几种算法（图解+演绎）

最短路径最短路径的求取有两种经典的算法，分别是Dijkstra算法和Floyd算法这Dijkstra算法的算法思想是基于贪心算法的，也就是选择权值最小的边而Floyd算法的算法思想是根据动态规划，不断迭代取得的Dijkstra算法：从顶点出发，优先选择与连接两个顶点集合中的权值最小的边，求单源最短路径Floyd算法：求多源最短路径，不断迭代列表中的数据DijkstraDijkstra算法的核心是实

浙桐

11491人浏览 · 2021-02-08 09:53:40

浙桐 · 2021-02-08 09:53:40 发布

最短路径

最短路径的求取有两种经典的算法，分别是Dijkstra算法和Floyd算法

这Dijkstra算法的算法思想是基于贪心算法的，也就是选择权值最小的边

而Floyd算法的算法思想是根据动态规划，不断迭代取得的

Dijkstra算法：从顶点出发，优先选择与连接两个顶点集合中的权值最小的边，求单源最短路径

Floyd算法：求多源最短路径，不断迭代列表中的数据

Dijkstra

Dijkstra算法的核心是实时更新三个列表信息构成的 —— 这与最小生成树中的Prim算法相似

第一个列表visited，是判断是否已选访问过改点，若为true，表示顶点已被访问，若为false，表示顶点未被访问，初始为false；

第二个列表minDist，表示两个点之间的距离，初始为∞（无穷大）；

第三个列表parent，存放它的双亲结点，初始为-1

整个生成过程是，首先（Update）更新列表信息，从列表下标由小到大更新minDist（记录整个路径长度）列表
然后（Scan）扫描整个列表，更新parent列表
最后（Add）将选择的点添加到已选顶点中，也就是更新visited列表

图示过程

有如下图，共有5个顶点，10条边，边的权值如下

首先选择顶点1，更新visited，顶点1的visited的值为T（Add）。

与此同时，与顶点1相连接的顶点分别为顶点2和顶点5，边权分别为10和5。因为10和5均小于inf（Update），所以更新minDist列表中顶点2和顶点5两个部分，同时需要将顶点2和顶点5的parent列表更新为1（Scan）如下图

在这里插入图片描述

由于权边5<10，顶点5的列表visited的值为F，所以更新visited，使顶点5的visited的值为T（Add）。

与此同时，与顶点1、顶点5相连接的顶点分别为顶点2、顶点3和顶点4，边权分别为10，3，9，2。因为9和2均小于inf,权值3小于权值10（Update），所以更新minDist列表中顶点2、顶点3和顶点4三个部分，同时需要将顶点2、顶点3和顶点4的parent列表更新为5（Scan）

在这里插入图片描述

由于权边在标绿色的权边，2最小，顶点4的列表visited的值为F，所以更新visited，使顶点4的visited的值为T（Add）。

与此同时，与顶点1、顶点5和顶点4相连接的顶点分别为顶点2、顶点3，边权分别为10，3，9，6，7。此时权值最短路径即为当前最短，不需要更新（Update），在最短路径不需要更新的情况下，parent列表也不需要更新（Scan）如下图

在这里插入图片描述

由于权边在标绿色的权边，3最小，顶点2的列表visited的值为F，所以更新visited，使顶点2的visited的值为T（Add）。

与此同时，与顶点1、顶点5、顶点4和顶点2相连接的顶点为顶点3，边权分别为10，9，6，1。此时权值最短路径即为当前最短，不需要更新（Update），在最短路径不需要更新的情况下，parent列表也不需要更新（Scan）如下图

在这里插入图片描述

由于权边在标绿色的权边，1最小，顶点3的列表visited的值为F，所以更新visited，使顶点3的visited的值为T（Add）。

与此同时，所有顶点相连接，由于权值1<权值9（Update），所以更新minDist列表中顶点3这个部分，同时需要将顶点3的parent列表更新为2（Scan）如下图

在这里插入图片描述

Floyd

Floyd算法的基本思想是：递推产生两个n阶方阵序列，一个方阵D是： $D(−1),D(A),D(B),D(C),…,D(n)D^{(-1)}, D^{(A)},D^{(B)},D^{(C)}, \dots,D^{(n)}$ ，其中 $D^{(n)}[i][j]$ 用以记录从顶点 $v_i$ 到顶点 $v_j$ 的路径长度，n表示操行结点n的运算步骤；另一个方阵S是 $S(−1),S(A),S(B),S(C),…,S(n)S^{(-1)}, S^{(A)},S^{(B)},S^{(C)}, \dots,S^{(n)}$ ,其中 $S^{(n)}[i][j]$ 用以记录从顶点 $v_i$ 到顶点 $v_j$ 的路径上的下一个点，n表示操行结点n的运算步骤。

初始情况，若两个顶点之间存在边，在方阵D记录边的权值，若不存在直接联系，就记录为inf；方阵S记录路径上的下一个点，初始状态就是该点本身。

解释： $D^{(A)}[i][j]$ 表示从顶点 $v_i$ 到顶点 $v_j$ 必经过结点A

存在一个图由3个顶点和5条有向边组成，初始状况下的方阵D和方阵S如下：

在这里插入图片描述

由图可知

从A到B，从A到C都可以直接到达；

从B到A可以直接到达，从B到A到C的权值和 $B A + A C = 10 + 13 = 23$ 大于4，所以不更新；

从C到A可以直接到达，从C到A到，此时权值为 $C A + A B = 5 + 6 = 11$ ，因为 $11 < i n f$ ，所以更新方阵D横轴为C纵轴为B这个方格中的数据， $i n f \to 11$

与此同时，需要更改方阵S横轴为C纵轴为B这个方格中的数据，B→A

在这里插入图片描述

由图可知

从A到B可以直接到达和从A到B到C的权值和为 $A B + B C = 6 + 4 = 10$ 小于13，所以更新方阵D横轴为A纵轴为C这个方格中的数据， $13 \to 10$ ；

与此同时，需要更改方阵S横轴为A纵轴为C这个方格中的数据，C→B

从B到A，从B到C均可以直接到达，所以不更新；

从C到B到A，此时权值为 $i n f + B A = i n f$ ，因为 $5 < i n f$ ，所以不更新；从C到B不直达，所以 $11 < i n f$ ，所以不更新

在这里插入图片描述

由图可知

从A到C到B的权值和为 $A C + C B = 13 + i n f = i n f$ 大于于6，所以不需要更新；从A到C可以直接到达，不需要更新

与此同时，需要更改方阵S横轴为A纵轴为C这个方格中的数据，C→B

从B到C到A的权值和为 $B C + C A = 4 + 5 = 9$ 小于10，需要更改方阵D横轴为B纵轴为 A1个方格中的数据， $10 \to 9$ ，从B到C均可以直接到达，所以不更新；

与此同时，需要更改方阵S横轴为B纵轴为A这个方格中的数据，A→C

从C到A可以直接到达，不需要更新；从C到B不直达，所以 $11 < i n f$ ，所以不更新

在这里插入图片描述

魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

【计算机视觉】Pixel逐像素分类&Mask掩码分类理解摘要

魔乐社区

计算机视觉（opencv）实战三十二——CascadeClassifier 人脸微笑检测（摄像头）

本文从原理到实现，详细介绍了基于 OpenCV Haar 分类器的人脸与微笑检测：讲解了 Haar 特征和级联检测原理。对代码逐行拆解并解释参数含义。画出完整流程图，帮助理解执行过程。给出了常见问题和优化建议，甚至扩展到深度学习方法。这种方法简单、轻量、实时性好，非常适合入门和小型应用项目。但如果需要更高准确率和更强鲁棒性，建议使用深度学习检测器替代 Haar 分类器。