单源最短路径问题 - 三大算法

• 从单源出发的正数有权图：Dijkstra（迪杰斯特拉）算法（时间复杂度为 O((V+E)lnV)
• 从单源出发的（可含有负权）有权图：Bellman‐Ford（贝尔曼‐福特）算法（时间复杂度为 O((V-1)E))
• 任意两点的有权图（可含有负权）：Floyd(弗洛伊德)算法

但均不支持​负权环 ，均支持有向图和无向图

注意含有负权的无向图=含有负权环（因为无向=双向）

由于无向图可以等价于双向有向图,所以后面全部当成有向图来分析

一、Dijkstra（迪杰斯特拉）算法

基本思想：最短路径的子路径也是最短路径、贪心算法

应用场景：从单源出发的正权有权图

伪代码如下：

​​

举例详细说明详细步骤：

​​

1. 初始化列表

​​

Visited：表示有无标记（初始化为 F）

Distance：表示从起点到该点的距离（初始化为无穷）

Parent：表示该点前面的点

记起点为 O

2. 每次从未标记的节点中选择 distance 最小的点 A，标记，收入到最优路径集合中
3. 计算节点 A 所有指向且尚未标记的相邻点 B 的距离，若 d(OA)+d(AB)<d(OB)，则更新 B 点的 distance，更新 B 的 parent 为 A

最后根据 Parent 从终点一直向前检索到起点即可得到最短路径

二、Bellman‐Ford（贝尔曼‐福特）算法

应用场景：从单源出发的无负环的有权图

可以处理含有负权的情况，伪代码如下：

​​

这个代码少了更新 parent

与 Dijkstra（迪杰斯特拉）算法不同的是，该算法不在乎节点是否访问，而是遍历所有边，检查是否可以松弛，这个操作要进行 V-1 次也就是总共要检查（V-1）E 次边

什么叫做松弛操作：

定义 d(u)为 u 到起点的距离

RELAX(u,v,weight(u,v))其中 u 为起点，v 为终点，weight(u,v)为该边的权重

检查是否 d(u)+weight(u,v)<d(v)，如果是则更新 d(v)和 parent(v)

三、Floyd(弗洛伊德)算法

与 Bellman‐Ford（贝尔曼‐福特）算法不同的是：Floyd 可以计算任意两点之间的最短路径

算法原理：依次选择每个点作为​中间点，更新​所有距离

1. 初始化表格 D(-1)与 Path(-1)

D 表示 distance;Path 表示 parent 即当前最优路径的前一个点

行为起点，列为终点

​​

2. 选取 0 为第一个中间点，计算 D(0)与 path(0)

​​

​​

我们发现 0 所在行列以及对角线都不需要改动

​​

对比发现 d(2,1)>d(2,0)+d(0,1)，所以更新 distance 和 parent

3. 同理接着计算以 1 为中间点和以 2 为中间点

​​

​​

这样的操作做 V 次使得每个点都做过中间点即完成算法

比如我想知道 2 到 1 的最短路径：那么就是 2-0-1