【学习笔记】最短路

本文同步在洛谷博客上进行发表。

给定一个有 $n$ 个点，$m$ 条有向边的图。请你计算从 $s$ 出发，到每个点的距离。

这就是经典的单源最短路径问题，我们可以用很多种算法来实现它。

注：

1. 下文所有 $n,m,k$ 均与上方引用语句含义相同。
2. 本文存图方式大多为链式前向星。
   由于下文不给完整程序，故补全链式前向星存图代码如下，方便读者理解下文的内容：

int h[NR], tot;
struct Edge
{
int u, v, w, next;
} e[NR];
void add(int u, int v, int w)
{
tot++;
e[tot].u = u, e[tot].v = v, e[tot].w = w;
e[tot].next = h[u], h[u] = tot;
}

不会链式前向星的读者请看这篇文章。

算法 $1$ : $\text{Floyd}$

$\text{Floyd}$ 是一个全源最短路径算法。它的本质是 $\text{DP}$。

状态表示：$di{s}_{i,j,k}$ 表示 $i$ 到 $j$ 间任意一条路径的中间结点（不含两端）编号 $\in [1,k]$ 时，$i,j$ 间最短路径的长度。
状态转移：$di{s}_{i,j,k}=\min (di{s}_{i,j,k-1},di{s}_{i,k,k-1}+di{s}_{k,j,k-1})$

三维的状态可以进行降维，把 $k$ 那维压缩掉。但是注意降维后必须优先枚举 $k$。

简化状态：$di{s}_{i,j}$ 表示 $i$ 到 $j$ 间最短路径长度。
状态转移：$di{s}_{i,j}=\min (di{s}_{i,j},di{s}_{i,k}+di{s}_{k,j})$

这里 $dis$ 其实是个邻接矩阵。

核心代码：

for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

时间复杂度：$O(n^3)$

优点：代码好写，可以处理带负权边的情况。
缺点：时间复杂度较高，不能处理负环。

算法 $2$ : $\text{SPFA \& Bellman-Ford}$

$\text{SPFA}$ 算法是老古董 $\text{Bellman-Ford}$ 算法的队列优化版本，它们都是单源最短路径算法。

定义数组 $dis$，$di{s}_i$ 为 $i$ 号结点到 $s$ 的距离。

先来讲讲 $\text{Bellman-Ford}$ 算法：

1. 遍历所有边，对于每条单向边（$u$ 到 $v$，边权为 $w$），$di{s}_v=\min (di{s}_v,di{s}_u+w)$
2. 重复上述操作 $(n-1)$ 次。

时间复杂度：$O(nm)$

我之所以将这个算法称为“老古董”，是因为它已经过时了。它的优化版本 $\text{SPFA}$ 算法才是重头戏。$\text{SPFA}$ 可以减少判断次数，从而获得更高的效率。

因为只有更新过 $u$ 的 $v$ 才对 $v$ 做出了贡献，所以我们定义一个先进先出的队列保存 $v$（$u,v$ 见上文讲解 $\text{Bellman-Ford}$ 算法时的定义），不断进行取队首并更新的操作，直到队列为空，即无结点可以更新。此时最短路径就找到了。

感觉实现起来像广搜。

核心代码：

queue <int> q;
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0; vis[s] = true; q.push(s);
while (!q.empty())
{
int u = q.front(); q.pop(); vis[u] = false;
for (int i = h[u]; i > 0; i = e[i].next)
{
int v = e[i].v, w = e[i].w;
if (dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
if (!vis[v]) q.push(v), vis[v] = true;
}
}
}

时间复杂度：$O(km)$

优点：可以出现负权边，可以判负环，稀疏图中效率高。
缺点：稠密图中 $\text{Bellman-Ford}$ 到 $\text{SPFA}$ 的优化几乎毫无作用，甚至有可能被卡到 $O(nm)$。举个例子，在 NOI 2018 Day1 T1 归程 中，凉心出题人就卡了 $\text{SPFA}$。因此衍生出一个梗：

关于 $\text{SPFA}$：它死了。

言归正传，$\text{SPFA}$ 还是有它独一无二之处的。它是能判负环的算法（也就两个，另一个是 $\text{Bellman-Ford}$）中最快的。

判断负环很简单，只要把上面代码拿出来改一改就行了。所以我们先讲思路。

思路不难，但是有点坑。这篇题解对我启发很大，尤其是这句话，请读者务必理解：

不能判松弛次数，要判入队次数！

定义 $cnt$ 数组，$cn{t}_i$ 表示 $i$ 号结点的入队次数。若 $cn{t}_i\ge n$（具体为什么见上文 $\text{Bellman-Ford}$ 算法讲解，理论上没有负环只需判断最多 $(n-1)$ 次），则说明入队次数超过了阈值，所以必有负环。

核心代码：

把上面代码的这句话：

if (!vis[v]) q.push(v), vis[v] = true;

稍作修改，变成：

if (!vis[v])
{
q.push(v); vis[v] = true; cnt[v]++;
if (cnt[v] >= n) return puts("YES"), 0;
}

算法 $3$ : $\text{Dijkstra}$

$\text{Dijkstra}$ 算法依旧是一个单源最短路径算法。它的堆优化版本也是最短路中效率较高，应用最广的算法。本质是个贪心。

先来讲一下不带优化的版本，大致可分为三个步骤。

1. 寻找结点 $u$，使所有未被标记的点中 $di{s}_u$ 最小，并标记 $u$。
2. 遍历所有以 $u$ 为起点的单向边（终点为 $v$，边权为 $w$），$di{s}_v=\min (di{s}_v,di{s}_u+w)$
3. 重复前两步，直到所有点都被标记。

核心代码：

memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
for (int i = 1; i < n; i++)
{
int u = 0;
for (int j = 1; j <= n; j++)
if (!vis[j] && (u == 0 || dis[u] > dis[j])) u = j;
vis[u] = true;
for (int j = h[u]; j > 0; j = e[j].next)
{
int v = e[j].v;
dis[v] = min(dis[v], dis[u] + e[j].w);
}
}

时间复杂度：$O(n^2)$

这个复杂度依然可以优化。我们发现，朴素的 $\text{Dijkstra}$ 在寻找 $dis$ 值最小的未标记结点时，时间复杂度是 $O(n)$ 的，完全可以用优先队列进行优化。

定义一个结构体 $\text{Node}$：

struct Node
{
int id, dist;
bool operator < (const Node &x) const
{
return dist > x.dist;
}
};
priority_queue <Node> q;

$id$ 表示结点编号，$dist$ 表示从 $id$ 到 $s$ 的最短路径长度。
重载运算符作用有两个：

1. 使大根堆变成小根堆
2. 按距离关键字排序

由此我们可以得出结论：定义的优先队列将会按每个结点到 $s$ 的最短路径长度从小到大进行排序。

优化完成。

核心代码：

memset(dis, 0x3f, sizeof(dis));
dis[s] = 0, q.push((Node){s, 0});
while (!q.empty())
{
int u = q.top().id; q.pop();
if (!vis[u])
{
vis[u] = true;
for (int i = h[u]; i > 0; i = e[i].next)
{
int v = e[i].v, w = e[i].w;
if (dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
q.push((Node){v, dis[v]});
}
}
}
}

时间复杂度：$O((n+m)\log n)$

优点：效率极高。
缺点：不能出现负权边，不能处理负环。

总结

数据小的题目：用 $\text{Floyd}$。
判断负环或有负权边：用 $\text{SPFA}$。
带非负权边的图：用 $\text{Dijkstra}$ + 堆优化。

最后

以上就是温暖老鼠为你收集整理的【学习笔记】最短路的全部内容，希望文章能够帮你解决【学习笔记】最短路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。