最短路

最短路问题

在一张图中，有 $n$ 个点， $m$ 条边，每条边有一个权值，给定起点 $s$ 和终点 $t$ ，在所有路径中选取一条权值和最小的路径，这就是最短路问题。

最短路的实现

DFS和BFS

如果一张图的规模比较小，我们便可以利用DFS搜索每一条路的权值，不断维护一个最小值，最终就能找到权值和最小的一条路。这种方法实现起来比较简单，但相应的时间复杂的比较高，而且只能够求两点之间的最短路。

如果一张图没有给定权值，我们便可以将每条路的权值设为1，利用BFS逐层延伸，其中BFS的层数即为路径长度，这样我们就可以求出某一点到剩余所有点的最短路了。但这种方法无法处理带权值且权值不相等的图。

接下来我们会介绍一下在最短路问题中常用的算法。

Floyd算法

在这个算法中，我们用到了动态规划的思想。对于图上任意两点 $i, j$ ，我们枚举图中所有的点，一旦发现存在某个点 $k$ 使得点 $i$ 经过其到达 $j$ 的距离比已知的点 $i$ 到点 $j$ 的距离小，我们就对其更新。状态转移方程为： $d_{i,j} = min\{d_{i,k} + d_{k,j}, d_{i,j}\}$

知道这个之后，我们便可以枚举图中所有的点，更新它们之间的最短路，从而得到任意点到任意点的最短路。核心代码如下：

void floyd()
{
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

由于我们初始化所有路径为INF，所以在第三层循环前可以加一个判断：

1	if(d[i][k] != INF)

即如果不存在 $i$ 到 $k$ 的路就结束，可以节省一点时间。总体而言，Floyd算法可以计算出图中任意点到任意点的最短路，即全源最短路。但是由于其有三层循环，所以时间复杂度为 $O(n^3)$ ，只能用于小规模数据。

Bellman-Ford算法

前面介绍的Floyd算法通常用于求全源最短路，如果我们想求单源最短路，可以考虑接下来介绍的算法。现在我们给定一个起点 $s$ ，定义数组 $d[]$ 记录任意一点到 $s$ 的最短距离。

在真正开始介绍算法之前，我们先了解一下松弛操作，即：

1	d[j] = min(d[j], d[i] + e[i][j]) // e[i][j] 指i到j的距离

为什么说是松弛呢，我们可以理解为本来两点间以一根紧绷的弹簧连接，而现在我们用两根较松的弹簧间接地连接两点，让其变松。经过一次松弛操作后，该点到起点的距离一定不大于松弛操作前的距离，所以松弛操作就是我们算法的核心。

知道了松弛操作之后，我们便可以开始求最短路了。假设存在一条最短路，它的路径为 $s \rightarrow p_1 \rightarrow p_2 \rightarrow ... \rightarrow t$ ，那么我们求出它的步骤如下：

松弛 $s,p_1$
再松弛 $p_1, p_2$ ，得到子最短路 $s \rightarrow p_1 \rightarrow p_2$
依次类推，松弛 $p_2,p_3$

那么，我们怎样才能保证每次都能松弛到位呢，答案是每次松弛时，把所有边都松弛一遍。那么一共需要松弛多少次呢，我们不难发现，每次松弛操作都至少有一个点的距离更新。而一张图一共有 $n$ 个点，所以我们只需要松弛 $n$ 次即可。核心代码如下：

struct edge
{
    int u, v, w;
} e[maxn]; //存边

void bellman-ford()
{
    for(int i = 1; i <= n; i++) //n次操作
        for(int j = 1; j <= m; j++) //枚举所有边
        {
            int x = e[j].u, y = e[j].v;
            d[y] = min(d[y], d[x] + e[j].w); //松弛操作
        }
}

除了寻找最短路，Bellman-Ford算法还可以判断负圈。因为如果存在负圈，就会有某些点可以不断更新距离，而如果不存在负圈，在 $n$ 次操作后，应该不会有点还能继续更新。所以，我们只需要判断在 $n$ 次操作后是否有点能够继续更新即可。

由于该算法有 $n$ 轮操作，每轮操作需要遍历 $m$ 条边，所以时间复杂度为 $O(nm)$ 。

SPFA

~~关于SPFA，它死了~~

上面我们介绍的Bellman-Ford算法，由于我们每次操作都松弛所有的边，所以会产生很多无用操作，使得时间复杂度大大上升，所以我们考虑对其进行优化，于是SPFA算法诞生了。SPFA算法实际上就是用队列优化的Bellman-Ford算法，初始起点入队，对后面的每轮操作，经过分析发现我们只需要经过松弛操作后距离更新的点(距离没更新的点肯定不在最短路中)，所以我们只需要枚举这些点相连的边即可。于是，如果松弛操作后该点的距离被更新且不在队列里，就入队。一直进行这样的操作，直到队列为空。核心代码如下：

struct edge
{
    int to, w;
    edge(int to = 0, int w = 0) : to(to), w(w) {}
};
vector<edge> e[maxn]; //邻接表存图

void SPFA()
{
    queue<int> que;
    que.push(s);
    inq[s] = 1; //判断是否在队里
    d[s] = 0; //距原点的距离
    
    while(!que.empty())
    {
		int u = que.front();
        que.pop();
        inq[u] = 0;
        for(int i = 0; i < e[u].size(); i++) //枚举相连的边
        {
            int v = e[u][i].to;
            if(d[v] > d[u] + e[u][i].w) //松弛操作
            {
                d[v] = d[u] + e[u][i].w;
                if(inq[v] == 0) //不在队中就入队
                {
                	que.push(v);
                	inq[v] = 1;
                }
            }
        }
    }
}

经过这样的优化后，SPFA算法在随机图中的复杂度可以来到 $O(kn)$ ，已经是相当快的速度了。当然，我强调了是随机图，这也说明了SPFA算法是不稳定的，经常会被卡时间，退化成与Bellman-Ford算法一样的时间复杂度。所以如果是保证没有负权的图，请使用接下来介绍的Dijkstra算法；如果有负权的话，Bellman-Ford也应是正解，所以SPFA算法在笔者看来，就最短路问题而言大可不必。

Dijkstra算法

对于一张没有负权值的图，我们可以使用Dijkstra算法来寻找最短路。Dijkstra算法的本质就是维护两个集合，一个是已确定最短路的集合 $A$ ，另一个是以确定最短路的点的邻居的集合 $B$ ，其实现步骤如下：

将起点 $s$ 加入 $A$ 集合，起点的邻居加入 $B$ 集合；
将 $B$ 集合中距离最小的点加入 $A$ 集合，并将新加入的这个点的邻居加入 $B$ 集合，如果存在多个相同的点，只保留距离最小的点；
重复上述步骤，直到 $B$ 集合为空。

正确性证明

不难发现，Dijkstra算法用到了贪心的思想，每一次都抄近路走。那么为什么这种方法是正确的呢，我们不妨用数学归纳法证明：

第一次加入的点 $v_1$ 显然是最短路；
假设第 $k$ 次加入节点 $v_k$ 后为最短路，此时集合 $A=\{s,v_1,...,v_k\}$ ，现在证明第 $k+1$ 次加入后仍为最短路；
假设第 $k+1$ 次加入节点 $v_{k+1}$ 后没有构成最短路，说明集合 $B$ 中存在一个点 $v_u$ 能构成最短路，则 $d[v_u] < d[v_{k+1}]$ 。而我们每次加入都是选取 $d$ 最小的点加入，即 $d[v_{k+1}] <= d[v_u]$ ，矛盾，假设不成立，即第 $k+1$ 加入后仍为最短路。

复杂度分析

$B$ 中初始会有 $n$ 个点，所以将所有点插入会执行 $n$ 次；每次点出集合都要对边进行松弛，一共进行 $m$ 次；每次找点时都会顺序遍历所有的点，一共执行 $n$ 次。所以，总时间复杂度为 $O(n^2 +m)$ 。

堆优化

分析后我们发现朴素的Dijkstra算法的复杂度跟Bellman-Ford一样，这解决不了数据大的问题，哪有没有办法优化呢？答案是可以。仔细观察我们的复杂的分析，发现找点的过程实际上是可以优化的，我们可以通过维护一个小顶堆，这样我们每次只要取出堆顶元素即可，这样的话找点的复杂的就优化到了 $O(logn)$ ，但是这样的每次取出元素松弛时堆结构发生了改变，所以松弛操作变慢了，总复杂度为 $O((n+m)logn)$ 。

优化后核心代码如下：

struct edge
{
    int to, w;
    edge(int to = 0, int w = 0) : to(to), w(w) {}
};
struct node
{
    int id, dis; //id为点的编号，dis为到起点的距离
    node(int id = 0, dis = 0) : id(id), dis(dis) {}
};
bool operator < (node x, node y)
{
    return x.dis > y.dis; //重载小于号，方便构建小顶堆
}
vector<edge> e[maxn]; //邻接表存图

void dijkstra()
{
    d[s] = 0;
    priority_queue<node> Q; //小顶堆
    Q.push(node(s, d[s]));
    
    while(!Q.empty())
    {
        node u = Q.top(); //取出堆顶元素
        Q.pop();
        if(check[u.id])
            continue; //懒惰删除，如果这个点的最短路已经找到了，就删除剩余相同的点
        for(int i = 0; i < e[u.id].size(); i++)
        {
            edge v = e[u.id][i];
            if(check[v.to]) //懒惰删除
                continue;
            if(d[v.to] > u.dis + v.w)
            {
                d[v.to] = u.dis + v.w;
                Q.push(node(v.to, d[v.to]));
            }
        }
	}
}