图论之最短路

2019-11-06 07:56:35

字体：大中小

来源：转载

供稿：网友

先小小理解一下： Dijkstra算法是我知道一个点像求最小生成树一样我自己找这个点以下的每个点，不一定按顺序吧；而Floyd算法是我有一个点，我遍历所有相连的点，是按顺序遍历的。至于Bellman-Ford和SPFA算法，我他么连名字都没背下来，更是没搞懂他俩了QAQ 储备一下： 1.

if(d[y]>d[x]+w[x][y]){ d[y]=d[x]+w[x][y]; fa[y]=x;} //松弛操作，常用于最短路

2. 给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度，即路上各边权之和。这个问题通常称为单源最短路问题。

Dijkstra算法：适用于边权为正的情况。

该算法同时适用于有向图和无向图。

Dijkstra算法和最小生成树PRim算法最小生成树算法非常类似，两个算法都是基于贪心算法。

这里模仿MST(Minimum Spanning Tree)的Prim算法步骤: a.我们创建一个SPT(最短路径树)，最初只包含源点。 b.我们维护两个集合，一组已经包含在SPT(最短路径树)中的顶点S集合,另一组是未包含在SPT内的顶点T集合。 c.每次从T集合中选择到S集合路径最短的那个点，并加入到集合S中，并把这个点从集合T删除。直到T集合为空为止。

解释一下为什么不能处理负的权值： Dijkstra算法是一种贪心算法。每次寻找距离源最短的点。然后在这个点上面进行松弛操作。如果有负权，则这种贪心在本质上就不成立，如图（红字表示权值）：这里写图片描述由算法知从顶点 1 到顶点 3 的最短路径为 1→3，其长度为 1 ，而实际上最短路径为 1→2→3 ，其长度为 0. （因为过程中先选择 v3 ， v3 被标记为已知，今后不再更新），所以不能处理负值。

除了求出最短路径，Dijkstra算法也能打印路径，即源点0到其他所有源点的路径。

现在的时间复杂度为O(n²)，为了优化它到O(mlogn)，可以采用优先队列+邻接表，师哥当时讲的堆优化实在是没理解╮(╯_╰)╭，然鹅我却查到堆是神奇的优先队列O.O。参考博客明白了Dijkstra算法的用处表达清晰搞懂了Dijkstra算法

Bellman-Ford 算法：求含负权图的单源最短路径算法。

为了能够求解边上带有负值的单源最短路径问题，Bellman(贝尔曼，动态规划提出者)和Ford(福特)提出了从源点逐次绕过其他顶点，以缩短到达终点的最短路径长度的方法。 Bellman-ford算法是求含负权图的单源最短路径算法，效率很低，但代码很容易写。即进行不停地松弛，每次松弛把每条边都更新一下，若n-1次松弛后还能更新，则说明图中有负环，无法得出结果，否则就成功完成。 ——为什么是n-1次呢？ ——因为在边权可正可负的图中，环有零环，正环，负环3种。如果包含零环和正环的话，去掉以后路径不会变成，如果包含负环则最短路是不存在的（tell me why ?若存在负环就会来回走直到-inf没有最短路）。那么既然不包含负环，所以最短路除了源点以外最多只经过n-1个点，这样就可以通过n-1次的松弛得到源点到每个点的最短路径。 Bellman-ford算法有一个小优化：每次松弛先设一个flag，初值为FALSE，若有边更新则赋值为TRUE，最终如果还是FALSE则直接成功退出。