历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 853. 有边数限制的最短路原题链接简单

作者：

Philosober , 2022-03-17 19:56:28 , 所有人可见 , 阅读 394

7

4

算法基础课笔记目录

最短路问题：Bellman-Ford算法

解决如下问题

Q：为什么Bellman_Ford算法需要$last$数组进行备份
Q：为什么$dist[e.b] = min(dist[e.b], last[e.a] + e.w)$中是$dist[e.b]$而不是$last[e.b]$
Q：什么是串路现象
Q：Bellman_Ford怎么判断负环
Q：Bellman_Ford为什么可以处理负权回路，而Dijkstra不行
Q：Bellman_Ford的本质思想是什么
Q：Bellman_Ford有什么不足之处吗（例如：搜索了不必要的点）

Bellman-Ford算法求最短路

算法思路

内层循环中，只要数组$dist[N]$发生了变化，则说明
松弛式：$$dist[b] = min(dist[b],\ dist[a] + w)$$
一定是式中的$dist[a]$变小了，那么可以断言：
如果$\forall \ node$，其邻接点$node_{aj}$的$dist$都不再改变，则$node$的$dist$也一定不会再改变；从而所有点的最短路就确定了
外层循环中，加以备份数组$last$进而比对这一次的$dist$和$last$是否发生了变化。如果没有变化，则继续直到充分松弛。
通过上述思路，可以显然看出：Bellman-Ford算法可以处理负权最短路问题
Q：为什么$Dijkstra$不能处理负权回路，而$Bellman-Ford$可以处理负权回路

那么，上述问题如何解决呢？其实很简单，我们只需要不采用贪心思维，不设置$S$集合，而是不断得去权衡$dist[b]$还能不能更小。另一方面，我们发现$dist[b]$更小只有一种可能，那就是$b$节点的邻接点的$dist$变小了。因此，更新点的本质是变小点和路径权重（只需要枚举边就可以了），从而我们得到了松弛式。通过不断用边去更新，便可以得到负权最短路了。
$$ dist[b] = min(dist[b], dist[a] + w) $$
当松弛操作全部结束（即：$dist$数组不再更新的时候），可以保证一定满足三角不等式：
$\forall b $ 和 $ \ \forall b_{aj} \ dist[b] \le dist[b_{aj}] + w$

void Bellman-Ford()
{
    dist[1] = 0,  dist[2~n] = +∞;
    while (更新后的dist和last不一样)   // 当没有点的dist更新时，说明不再有点的dist变小，因此是最短路
    {
        last = dist;  // 复制dist到last
        // 更新dist
        for (枚举所有边e)
            dist[e.b] = min(dist[e.b], dist[e.a] + e.w);
    }
}

注：有关于last数组的用途请继续往下看，这里求最短路是利用了串联现象来加速

时间复杂度分析

通过后面的结论，我们可以知道更新dist数组的次数具有实际意义：只用$k$条边到达任意点的最短距离
因此可以断言：要确保第$n$个点被充分松弛，则至多需要$n-1$次循环，因此外层最坏时间复制度为$O(n)$
内层循环中，由于一次更新操作需要用到全部的边，因此为$O(m)$
因此，总体的时间复杂度为：$O(nm)$

适用范围

有向，负权，稠密图（$m >> n$）

C++代码实现

注：这个代码默认是没有负权回路的，因此复杂度是低于$O(nm)$的，否则为了检测负权回路Bellman_Ford一定是$O(nm)$

#include <iostream>
#include <cstring>

using namespace std;
const int M = 100010;
int dist[M], last[M];
int n, m, k;

struct Edge
{
    int a, b, w;
} edges[M];


void Bellman_Ford()
{
    memset(dist, 0x3f3f3f3f, sizeof dist);
    dist[1] = 0;
    // 用while进行充分松弛（充分利用所有边）
    while (memcmp(last, dist, sizeof dist))  // 当dist不再更新时，则表明已经确定了所有最短路点
    {
        memcpy(last, dist, sizeof dist);
        for (int j = 1; j <= m; j ++)
        {
            Edge e = edges[j];
            dist[e.b] = min(dist[e.b], dist[e.a] + e.w); // 利用串联特性，让其更快得更新
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++)
    {
        int a, b, c;
        scanf("%d%d%d", &edges[i].a, &edges[i].b, &edges[i].w);
    }

    Bellman_Ford();

    if (dist[n] >= 0x3f3f3f3f)  printf("%d", -1);
    else printf("%d", dist[n]);

    return 0;
}

Bellman-Ford算法求限制边最短路

串联现象

要求：求限制边数为1的最短路

Bellman-Ford算法中的串联现象.png

数据结构：Edge数组Edge = [(1,2,1), (2,3,1), (1,3,3)]

流程：

先将dist[1] = 0，然后遍历到(1,2,1)，$dist$数组发生更新(0, inf, inf) -> (0, 1, inf)
再遍历到(2,3,1)，使得$dist$数组再次发生更新(0, 1, inf) -> (0, 1, 2)
到目前为止，第一轮跟更新完毕，但是我们可以发现$dist[3] = 2$，显然这是不对的。

限制边最短路

这是一个极为常见的问题，应用场景如下：

军队从$A$地赶往$B$地，如果避免被攻击，则路途很遥远；如果选择最近的路，则需要攻克几座城堡。这时，我们不光要考虑走哪条路径会使得路程最短，还要考虑到可能遭遇的城堡攻坚。比如：军队只能接受3次城堡攻坚，那么就得以3次攻坚为条件，寻找一条最短路。

Q：为什么限制外层循环的次数，等价于求限制边的最短路？

A：从$dist[1] = 0$开始，由于加入了$last$数组，第一次松弛只更新了$1$号点出边的邻接点，记作集合$A_1$。紧接着，第二次松弛更新了$A_1$的所有出边连接的点，记作集合$A_2$。注意到，此时集合$A_2$是$1$号点通过两条边所能到达的点。

Bellman-Ford算法中的限制边最短路原理.png

数学归纳法可以进行完整的证明

算法思路

把上一次的$dist$备份至$last$，确保不串联（即：防止在一次迭代中更新多条边的情况）
外层循环中的$k$具有实际意义：从$1 \to i，(i = 2, 3, …, n)$不超过$k$条边下的最短路径

void Bellman_Ford()
{
    dist[1] = 0, dist[2~n] = +∞;
    for (1~k)
    {
        last = dist;  // 备份dist数组
        for (所有边)
            dist[e.b] = min(dist[e.b], last[e.a] + w);
    }
}

时间复杂度分析

外层需要循环$k$次
内层循环依然是$m$条边
因此，总时间复杂度为：$O(km)$

适用范围

限制边，有向，负权，稠密图（$m >> n$）

C++代码实现

#include <iostream>
#include <cstring>

using namespace std;
const int N = 10010;
int n, m, k;
int dist[N], last[N];   // last为备份数组

struct Edge
{
    int a, b, w;
}edges[N];

void Bellman_Ford()
{
    dist[1] = 0;
    for (int i = 1; i <= k; i ++)
    {
        memcpy(last, dist, sizeof dist);
        for (int j = 1; j <= m; j ++)     // 第j条边
        {
            Edge e = edges[j];
            dist[e.b] = min(dist[e.b], last[e.a] + e.w);
        }
    }

    if (dist[n] >= 0x3f3f3f)  printf("impossible");   // 注意本题有负权回路
    else printf("%d", dist[n]);
}

int main()
{
    memset(dist, 0x3f3f3f3f, sizeof dist);
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i ++)  scanf("%d%d%d", &edges[i].a, &edges[i].b, &edges[i].w);
    Bellman_Ford();
    return 0;
}

Bellman-Ford算法求负权回路

算法思路

由于第$k$次循环，具有实际意义：不超过$k$条边的最短路径
因此，如果当$k = n$时$dist$数组还在更新，则说明出现了一条经过$n$条边的最短路径
经过$n$条边 <===> 经过$n + 1$个点，则说明某个点经过了两次，因此存在负权回路（负环）

模板跟原始的Bellman_Ford算法一致，只需要加入边数限制即可

时间复杂度

分析方式和之前一样，依然是$O(nm)$

适用范围

有向，负权，稠密图（$m >> n$）

C++代码实现

#include <iostream>
#include <cstring>

using namespace std;
const int N = 2010, M = 10010, INF = 0x3f3f3f3f;
int dist[N], last[N];
int n, m;

struct Edge
{
    int a, b, c;
} edges[M];

void Bellman_Ford()
{
    int times = 0;
    memset(dist, INF, sizeof dist);
    dist[1] = 0;

    while (memcmp(last, dist, sizeof dist) && times <= n)
    {
        times ++;
        memcpy(last, dist, sizeof dist);
        for (int i = 1; i <= m; i ++)
        {
            Edge e = edges[i];
            dist[e.b] = min(dist[e.b], dist[e.a] + e.c);
        }
    }

    if (times >= n)  printf("Yes");
    else printf("No");
}


int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = {a, b, c};
    }

    Bellman_Ford();

    return 0;
}