Dijkstra和弗洛伊德算法：计算数据结构图中最短路径的回顾总结

解决的问题是加权图中从一个顶点到另一个顶点的最短路径。这里我们主要讲Dijkstra算法和弗洛伊德算法。

1。Dijkstra的算法

1。定义说明

Dijkstra算法是典型的最短路径算法，用于计算从图或网络中给定顶点到所有其他顶点的最短路径，以起点为中心逐层展开，直至到达终点。 ，适合计算单源的最短路径，时间复杂度为O(N^2)。使用贪心方法。

2。算法思想

例如G=(V,E)是一个带权有向图。将图中的顶点集 V 分为两组。第一组是寻找最近路径的一组顶点。 （用S表示，第一个S中只有​​一个源点，如果以后找不到最短路径，则将其添加到集合S中，直到所有顶点都添加到S中，算法终止）。第二组是对于最短路径尚未确定的剩余顶点集（用U表示），第二组中的顶点被添加到S中以增加最短路径的长度。在连接过程中，源点 v 到 S 中各顶点的最短路径长度始终保持不大于源点 v 到 U 中任意顶点的最短路径长度。顶点对应于距离。 S 中某个顶点的距离是从 v 到该顶点的最短路径的长度。 U中顶点的距离是当前从v到该顶点的最短路径，仅包括S中的顶点作为中间顶点。路的长度。

2。弗洛伊德算法

1。定义与描述

Floyd算法是一种求解两点之间最短路径的算法。它可以很好地处理有向图或负权重的最短路径问题，也用于计算有向图的闭包。 Floyd算法的时间复杂度为O(N^3)

上图中有4个城市和8条高速公路。高速公路上的数字代表高速公路的长度。这条路都是单向的。我们需要找到两个城市之间最近的距离，

这个问题被称为“多源最短路径”问题。

2。算法思维

Floyd 是一个经典的动态规划问题。目标是找到从 i 到 j 的最短路径。从动态规划的角度来看，我们需要重新解释这个目标。从任意点i到任意点j的最短路径不超过两种可能。一是从i直接到j，二是从i经过一些节点k到j，所以我们假设Dis(i,j)是从顶点u到顶点v的最短路径的距离。对于每个顶点 k ，我们查看 Dis(i,k ) + D(k,j) > Dis(i,j) 正确吗？如果为真，则证明从 i 到 k 再到 j 的路径比从 i 直接到 j 的路径短。我们设Dis(i,j)= Dis(i,k) + Dis(k,j)，这样当我们经过所有顶点k时，Dis(i,j)中记录的就是该顶点的距离从 i 到 j 的最短路径。

3。算法步骤

从一个方向的边开始，两点之间的距离就是该边的权重。如果没有边连接两点，则权重是无限的。

对于每个顶点u和v，查看是否存在一个顶点w使得u到w到v比已知路径短，如果有则更新。