11.23 — 11.29 最短路径算法理解(Dijkstra算法和Floyd算法)
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开始,到各节点的最短路径)
具体执行步骤如下图所示:
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) 就行了。
搬运的执行步骤图解:
第一步,我们先初始化两个矩阵,得到下图两个矩阵(矩阵D中顶点a[i][j]的距离为顶点i到顶点j的权值,矩阵P中的元素b[i][j],表示顶点i到顶点j经过了b[i][j]记录的值所表示的顶点。):
第二步,以v1为中阶,更新两个矩阵:
发现,a[1][0]+a[0][6] < a[1][6] 和a[6][0]+a[0][1] < a[6][1],所以我们只需要矩阵D和矩阵P,结果如下:
通过矩阵P,我发现v2–v7的最短路径是:v2–v1–v7
第三步:以v2作为中介,来更新我们的两个矩阵,使用同样的原理,扫描整个矩阵,得到如下图的结果:
他每次都会选择一个中介点,然后,遍历整个矩阵,查找需要更新的值。
过程图转载自:https://blog.csdn.net/qq_35644234/article/details/60875818
推荐阅读
-
图的五种求最短路径算法(Dijkstra、堆优化Dijstra、Bellmon-Ford、SPFA、Floyd-Warshall)
-
python实现图的深度优先搜索(DFS)和广度优先搜索(BFS)算法及Dijkstra最短路径应用
-
#2020寒假集训#最短路入门(Floyd弗洛伊德 和 Dijkstra迪杰斯特拉 算法)代码笔记
-
图论之最短路1(Floyd和Dijkstra算法)
-
图论算法——Dijistra和Floyd算法求最短路径
-
图论——最短路径-Dijkstra算法和Floyd算法
-
图论(最短路径,Dijkstra算法和Floyd算法)
-
图的最短路径的Dijkstra算法和Floyd算法原理解析以及Java代码的实现
-
使用Dijkstra/Floyd算法解决最短路径问题
-
经典算法 - 最短路径问题与Dijkstra、Floyd算法