欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

11.23 — 11.29 最短路径算法理解(Dijkstra算法和Floyd算法)

程序员文章站 2022-03-15 08:37:57
...

Dijkstra(迪杰斯特拉)算法

主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止,类似于BFS,prim算法。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。 是很经典的最短路径算法。

搬运一个算法描述
(1)S为已经找到的从v出发的最短路径的终点集合,它的初始状态为空集,那么从v出发到图中其余各顶点(终点)vi(vi∈V-S)可能达到的最短路径长度的初值为:

     d[i] = arcs[LocateVex(G, v)][i],vi∈V

(2)选择vj,使得 d[j] = Min{d[i]|vi属于V-S},vj就是当前求得的一条从v出发的最短路径的终点。令S=S∪{j};

(3)修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。如果 d[j] + arcs[j][k] < d[k], 则修改d[k]为:d[k] = d[j] + arcs[j][k];

(4)重复(2),知道所有顶点都包含在S中,此时得到v到图上其余各顶点的最短路径是依路径长度递增的序列。

个人理解是,将结点分为两个集合S和U,S集合中初始存放源结点,U中存放剩下的结点。从源结点向外层层扩展,选择权值sum最小的路径,属于一种贪心算法。扫描过的结点从U中取出放入S集合中,直至U集合为空为止。

具体图例与算法执行步骤:
(从A开始,到各节点的最短路径)
11.23 — 11.29 最短路径算法理解(Dijkstra算法和Floyd算法)

具体执行步骤如下图所示:

11.23 — 11.29 最短路径算法理解(Dijkstra算法和Floyd算法)

Floyd(弗洛伊德)算法

弗洛伊德(Floyd)算法是解决任意两点间的最短路径的一种经典的动态规划算法,可以正确处理有向图或有向图或负权(但不可存在负权回路)的最短路径问题,同时也被用于计算有向图的传递闭包。

算法描述
1)首先把初始化距离dist数组为图的邻接矩阵,路径数组path初始化为-1。其中对于邻接矩阵中的数首先初始化为正无穷,如果两个顶点存在边则初始化为权重   
2)对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是就更新它。
假设Dis(i,j)为节点i到节点j的最短路径的距离
状态转移方程为
如果 dist [i][k] + dist [k][j] < dist[i][j]
则dist [i][j] = dist [i][k] + dist [k][j]

个人理解:从一个结点到另一个结点只会存在两种情况,一种是一个结点直接达到另一个结点(也就是不通过别的结点),另一种就是通过一个或者多个别的结点从而达到目标结点。 那么每一步骤只需要判断一下是否存在中间结点K 使得 Dis(i,k) + Dis(k,j) < Dis(i,j) 就行了。

搬运的执行步骤图解:
11.23 — 11.29 最短路径算法理解(Dijkstra算法和Floyd算法)

第一步,我们先初始化两个矩阵,得到下图两个矩阵(矩阵D中顶点a[i][j]的距离为顶点i到顶点j的权值,矩阵P中的元素b[i][j],表示顶点i到顶点j经过了b[i][j]记录的值所表示的顶点。):
11.23 — 11.29 最短路径算法理解(Dijkstra算法和Floyd算法)
11.23 — 11.29 最短路径算法理解(Dijkstra算法和Floyd算法)
第二步,以v1为中阶,更新两个矩阵:
发现,a[1][0]+a[0][6] < a[1][6] 和a[6][0]+a[0][1] < a[6][1],所以我们只需要矩阵D和矩阵P,结果如下:
11.23 — 11.29 最短路径算法理解(Dijkstra算法和Floyd算法)
11.23 — 11.29 最短路径算法理解(Dijkstra算法和Floyd算法)
通过矩阵P,我发现v2–v7的最短路径是:v2–v1–v7

第三步:以v2作为中介,来更新我们的两个矩阵,使用同样的原理,扫描整个矩阵,得到如下图的结果:
11.23 — 11.29 最短路径算法理解(Dijkstra算法和Floyd算法)
11.23 — 11.29 最短路径算法理解(Dijkstra算法和Floyd算法)
他每次都会选择一个中介点,然后,遍历整个矩阵,查找需要更新的值。

过程图转载自:https://blog.csdn.net/qq_35644234/article/details/60875818

相关标签: 周总