上帝之手——浅谈最短路问题算法

2023-02-12 11:29:24

问题引入

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的福大数计学院吉祥物公仔。但是每当我们的工作人员把上百件的吉祥物从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？（问题背景来源于生活）

题意转化

给定一个有边权的有向图 \(G(V, E)\)，起点 \(S\) 和终点 \(T\)，求一条从 \(S\) 到 \(T\) 的最短路径。

解决方案

深度优先搜索

简称最朴素最暴力的做法。深度优先算法的核心思想是顺着一条路一直走下去，不撞南墙不回头，直到遍历所有情况。这就好比是走迷宫，你沿着一条路要一直走，直到遇到死胡同才返回。形式化而言就是从一个点出发，递归 + 回溯遍历每一条与它相连的边，直至到达终点，更新最短路。

void dfs(int u)
{
    if (u == t)
        return ans = min(ans, val), void();
    for (auto [v, w] : G[u])
        val += w, dfs(v), val -= w;
}

但是此算法并不是完美的。对“时间复杂度”略有所知的同学可以清晰地发现，此算法的时间复杂度是和图上 \(S\) 到 \(T\) 的路径总数同阶的，而路径总数在具有某些特征的图上是可以达到指数级别的。举一个清晰的例子，比如当点数边数达到 40 ~ 50 的时候，一般计算机就无法在规定时间内得到答案。

Bellman-Ford 算法

由国外计算机科学家 \(Bellman\) 和 \(Ford\) 联合提出。定义一种“松弛”操作：如果存在某条边连接的两个点 \(u\) 和 \(v\) 满足 \(dis_v > dis_u + w\) ，则令 \(dis_v = dis_u + w\) 。设点数为 \(|V|\)，进行 \(|V| - 1\) 次循环，每次循环遍历图中所有的边，检查能否进行松弛操作，如果某次循环中没有松弛操作就停止循环。

\(Bellman-Ford\) 算法相比于深度优先搜索已经有了极大的改进，它使得解决问题的时间复杂度将至 \(O(n(n + m))\)。但是，在大数据规模的最短路问题中仍然显得心有余而力不足。

void Bellman_Ford()
{
    for (int i = 1; i <= n; i++) dis[i] = inf;
    
    dis[s] = 0;
    for (int i = 1; i <= n - 1; i++)
        for (int u = 1; u <= n; u++)
            for (auto [v, w] : G[u])
	            dis[v] = min(dis[v], dis[u] + w);
}

SPFA 算法

接下来介绍一个由国内研发出来基于 \(Bellman-Ford\) 的一个优化算法。定义一个队列 \(Q\)，记 \(dis_u\) 为当前 \(s\) 到 \(u\) 的最短路径长度。首先将起点 \(S\) 放进队列 \(Q\) 中；接下来每次从队列中取出队首节点 \(u\)，遍历与 \(u\) 相邻的所有点 \(v\)，设 \(u\) 到\(v\) 的路径长度为 \(w\)，如果 \(dis_v > dis_u + w\) ，则令 \(dis_v = dis_u + w\) 。重复这个操作直到队列为空。

void spfa()
{
    for (int i = 1; i <= n; i++) dis[i] = inf;
    for (int i = 1; i <= n; i++) exist[i] = 0;
    
    dis[s] = 0; exist[s] = 1; Q.push(s);
    while (!Q.empty())
    {
        int u = Q.front(); Q.pop(); exist[u] = 0;
        for (auto [v, w] : G[u])
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                if (!exist[v]) Q.push(v), exist[v] = 1;
			}
	}
}

对比于 \(Bellman-Ford\) 算法而言，\(SPFA\) 看似已经有了极大的改进。在随机图上，他的期望时间复杂度甚至达到了 \(O(m)\)。但是实际上而言，对于一些特殊构造的图上，它的时间复杂度依然是劣的：例如在网格图上，已经达到平方的复杂度。这在大数据规模的最短路问题上依然是不可接受的。

Dijkstra 算法

终于来介绍本文的主角，由著名计算机科学家 \(Dijkstra\) 提出的 \(Dijkstra\) 算法。该算法只能适用于非负边权图。

先来阐述一下该算法的流程：定义一个数据结构 \(Q\)（可以是数组之类的），记 \(dis_u\) 为当前 \(s\) 到 \(u\) 的最短路径长度。首先将起点 \(S\) 放进 \(Q\) 中；接下来每次从 \(Q\) 中取出 \(dis\) 值最小的节点 \(u\)，遍历与 \(u\) 相邻的所有还在 \(Q\) 中的点 \(v\)，设 \(u\) 到\(v\) 的路径长度为 \(w\)，如果 \(dis_v > dis_u + w\) ，则令 \(dis_v = dis_u + w\) 。重复这个操作直到 \(Q\) 为空。

使用 \(Dijkstra\) 算法求解最短路问题时的某个状态，其中黑点表示仍在 \(Q\) 中。此时 \(1\) 号点已从 \(Q\) 中取出，接下来应取出 \(6\) 号点

证明：先证明任何时候第一个集合中的元素的一定不大于第二个集合中的。再证明第一个集合中的元素的最短路已经确定。第一步，初始状态时必然成立（基础），在每一步中，加入集合的元素一定是最大值，且是另一边最小值，每次松弛操作又是加上非负数，所以仍然成立（归纳）（利用非负权值的性质）。第二步，考虑每次加进来的结点，到它的最短路，上一步必然是第一个集合中的元素（否则他不会是第二个集合中的最小值，而且有第一步的性质），又因为第一个集合内的点已经全部松弛过了，所以最短路显然确定了。

介绍了算法流程以及证明了正确性，接下来还有一个悬而未决的问题：数据结构 \(Q\) 应当是什么？

思考一下本算法中 \(Q\) 的用途：从中取出 \(dis\) 最小的元素以及加入元素。拥有数据结构基础的同学不难发现：这不就是个堆嘛？对，就是个堆（限于篇幅在此不做对堆的基本知识的赘述）。如果使用 C++ 进行编写 \(Dijkstra\) 算法的话，在 STL 库中有一个封装好的类叫做 \(priority\_queue\)（优先队列），它能够在 \(O(log_2n)\) 的复杂度能完成堆的基本操作。这样一来，综上所述我们最终优化出来的 \(Dijkstra\) 算法复杂度为 \(O((n + m) log_2n)\)。这已经能够解决当前工业学术界的绝大多数问题。

typdef pair<int, int> pii;
priority_queue<pii, vector<pii>, greater<pii> > Q;

void dijkstra()
{
    for (int i = 1; i <= n; i++) dis[i] = inf;
    for (int i = 1; i <= n; i++) done[i] = 0;
    
    Q.push(make_pair(dis[s] = 0, s));
    while (!Q.empty())
    {
        int u = Q.top().second; Q.pop(); 
        if (done[u]) continue;
        done[u] = 1;
        for (auto [v, w] : G[u])
            if (dis[v] > dis[u] + w)
                Q.push(make_pair(dis[v] = dis[u] + w， v);
	}
}

\(Dijkstra\) 是一种高效的最短路问题算法。但是他的缺点也很明显：只能适用于非负边权图。在 \(Dijstra\) 提出该问题后，又有 \(Johnson\) 提出了经典的 \(Johnson\) 算法，通过转化用以消除负边权使得 \(Dijkstra\) 再能显出“神通”。在当前的学术工业界中，\(Dijkstra\) 算法也为人工智能的寻路算法提供了一些启示，具有先进意义。

码农公寓