【学习笔记】最短路

Mysterious_Mini · 2021-08-10 14:08:00 · 个人记录

本文同步在 CSDN 上进行发表。

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

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

注：

下文所有 n,m,k 均与上方引用语句含义相同。
本文存图方式大多为链式前向星。

由于下文不给完整程序，故补全链式前向星存图代码如下，方便读者理解下文的内容：

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}

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

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

简化状态：dis_{i,j} 表示 i 到 j 间最短路径长度。

状态转移：dis_{i,j}=\min(dis_{i,j},\ dis_{i,k}+dis_{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}

定义数组 $dis$，$dis_i$ 为 $i$ 号结点到 $s$ 的距离。先来讲讲 $\text{Bellman-Ford}$ 算法： 1. 遍历所有边，对于每条单向边（$u$ 到 $v$，边权为 $w$），$dis_v=\min(dis_v,\ dis_u+w)

重复上述操作 (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 数组，cnt_i 表示 i 号结点的入队次数。若 cnt_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}

先来讲一下不带优化的版本，大致可分为三个步骤。 1. 寻找结点 $u$，使所有未被标记的点中 $dis_u$ 最小，并标记 $u$。 2. 遍历所有以 $u$ 为起点的单向边（终点为 $v$，边权为 $w$），$dis_v=\min(dis_v,\ dis_u+w)

重复前两步，直到所有点都被标记。

核心代码：

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) 的，完全可以用优先队列进行优化。

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

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

重载运算符作用有两个： 1. 使大根堆变成小根堆 2. 按距离关键字排序由此我们可以得出结论：定义的优先队列将会按每个结点到 $s$ 的最短路径长度从小到大进行排序。至此，优化完成。核心代码： ```cpp 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} + 堆优化。