图论 —— 求解最短路径（Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法）（求解最短路径的floyd算法的时间复杂度为( )）-九幽软件

图论 —— 求解最短路径（Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法）（求解最短路径的floyd算法的时间复杂度为( )）

1.最短路径

认识最短路径

最短路径的分类

2.单源最短路径

Dijkstra算法

Dijkstra算法的大致思想

Dijkstra算法的大致流程图

Dijkstra算法代码如下

Dijkstra算法的缺陷

Bellman-Ford算法

Bellman-Ford算法的大致思想

Bellman-Ford算法的大致流程

Bellman-Ford算法代码如下

Bellman-Ford算法的优缺点

3.多源最短路径

Floyd-Warshall算法

Floyd-Warshall算法的大致思想

Floyd-Warshall算法的大致流程图

Floyd-Warshall算法的代码

在现实生活中，我们当我们想要去其他地方的时候，而到达目的地的交通方式往往不止一种，我们往往会计算到达目的地的各种交通方式所花费的成本，计算成本不是目的，我们的目的是选择交通成本最小的路径，为了解决这种问题，就可以使用图论中的求解最短路径的算法 ——?Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法。其中，前两个是计算单源最短路径的算法，最后一个是计算多源最短路径的算法。

那什么是最短路径呢？最短路径就是从一点出发到达另一点的权值之和最小的路径。

比如在下面这个图中，我们想要从s点出发到达x点，我们有多条路径可以选择，比如：

s->t->x? 路径上的权值和为：11
s->y->x??路径上的权值和为：14
s->y->z->x??路径上的权值和为：13
s->y->t->x??路径上的权值和为：9

我没有枚举所有情况，但是我们应该可以看出s到x的权值和最小是9，路径为s->y->t->x，这条路径就是最短路径。

最短路径问题分为单源最短路径问题和多源最短路径问题。

单源最短路径求解的是从图中的一个顶点出发，到达图中所有顶点的最短路径。
多源最短路径求解的是同一个图中，任意两个顶点之间的最短路径。

求解单源最短路径的算法有Dijkstra算法（迪杰斯特拉算法）、Bellman-Ford算法（贝尔曼福特），求解多源最短路径的算法有Floyd-Warshall算法（弗洛伊德算法）。

Dijkstra算法的大致思想

将图G中的顶点分为两组，S和Q，S是已经确定最短路径的顶点集合，Q是还没有确定最短路径的顶点的集合，每次选择从集合S到集合Q中的权值最小的边，并将这条边的终点u从集合Q中移除并添加到集合S中，然后对u的每一个相邻顶点v进行松弛操作（贪心策略），直到集合Q中没有结点为止；松弛操作就是对每一个相邻顶点v，判断源结点s到u的代价和u到v的代价和是否小于原来的s到v的代价，将s到v的代价更新为两者中较小的那个。

注意：终点是不在集合S中的点。

我们可以分析一下贪心策略：每次选择集合S到集合Q中权值最小的边，这条边的起点在S中，终点在Q中，我们假设这条边的起点是start，终点是end，源结点为s；因为集合S是已经确定最短路径的顶点，那意味着s到start的代价是最小的，边（start，end）的权值也是最小的，两个最小相加就意味着s到end的代价是最小的。

s到end代价最小的路径是s->start2->end，代价和为4。?

Dijkstra算法的大致流程图

图中的**表示无穷大

最终，以顶点s为起始原点到达图中的所有顶点的最短路径如下：

s->s = 0
s->y = s->s->y = 0+5 = 5
s->z = s->s->y->z = 0+5+2 = 7
s->t = s->s->y->t = 0+5+3 = 8
s->x = s->s->y->t->x = 0+5+3+1 = 9

Dijkstra算法代码如下

Dijkstra算法的缺陷

Dijkstra算法存在的问题是不支持图中带负权路径，如果带有负权路径，则可能会找不到一些路径的最短路径?。

我们以下面这个图为例：以s为起始源点

运行结果如下：

可以看到s到x的最短路径没有更新出来，这是因为负权边的存在可能会导致Dijkstra算法的贪心策略失效。这是为什么呢？

如下图：

?当我们选择权值为-7的边的终点进行松弛操作的时候，无法将权值-7计算在最短路径中，从而导致贪心策略失效。

Dijkstra算法只能解决正权图的单源最短路径问题，但有些场景会出现负权图，Dijkstra算法无法解决，于是，有大佬发明了可以解决带负权的图的最短路径问题。

Bellman-Ford算法的大致思想

进行多轮更新，每一轮更新都要处理所有的边，最多更新n轮（n是图中的顶点个数）。

你肯定有疑问，为什么要更新n轮？这是因为，每一轮更新都要更新所有的边，但是由于遍历边的顺序可能导致原先需要改变的边没有改变，这个时候就需要再次更新就纠正了，所以我们最多需要跟新n次，相当于每次都能确定一个顶点的最短路径。

在Dijkstra算法的缺陷中，我们分析了为什么Dijkstra算法无法解决带负权的图的最短路径问题，其实就是不能将负权计算在路径中，说的通俗一点就是没有访问到，这一点和Dijkstra算法的松弛操作有关；于是，Bellman-Ford算法采用更加暴力的遍历方式，每一次的松弛操作都对所有的边进行更新。