冻葱Tewi
一个菜鸡。
冻葱Tewi
【算法】最短路基础小结

最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。算法具体的形式包括:

  • 确定起点的最短路径问题 – 即已知起始结点,求最短路径的问题。适合使用Dijkstra算法。
  • 确定终点的最短路径问题 – 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
  • 确定起点终点的最短路径问题 – 即已知起点和终点,求两结点之间的最短路径。
  • 全局最短路径问题 – 求图中所有的最短路径。适合使用Floyd算法。

前置知识

  • 了解图论中的基本概念。
  • 会用邻接矩阵、邻接表存图(包括链式前向星)。

文章约定

dis[p]/dis[p][q] 从起点到p点的最短距离/从p到q的最短距离
edge[][] 邻接矩阵/邻接表/Edge类数组
INF = 0x3f3f3f3f 即用0x3f做memset()参数的结果,足够大而且可以保证无穷+无穷=无穷的性质

Floyd算法

思路与实现

Floyd算法是我接触的所有最短路算法当中方法最为朴实易懂的一种算法,运用了动态规划的思想。时间复杂度\(O(n^3)\)。

这个算法的主要思路,就是遍历每个断点,看能否通该点进行中转来使另外两点之间的最短距离变少,即每次循环寻找从i号点到j号点只经过前k个点的最短路程

核心代码:

for (int k = 1; k <= n; k++) // 枚举中转点
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (dis[i][j] > dis[i][k] + dis[k][j]) // 查看能否通过该点更新最短距离
            {
                dis[i][j] = dis[i][k] + dis[k][j];
            }
        }
    }
}

为什么说Floyd本质上是一种动态规划呢?因为可以看做状态转移方程为

$$
f(k, i, j) = min(f(k-1, i, k),\ \ f(k-1, i, k) + f(k-1, k, j))
$$

的多维DP(而且这种好几层循环的码风也特别像DP)

相关题目

洛谷P1119 – 灾后重建

题目中所给的边分别在某个时间才能开始使用,那么只要将边按通车时间排序,然后进行Floyd即可。

核心代码:

inline void floyd(int k) // 提供断点k
{
    for (int u = 0; u < n; u++)
    {
        for (int v = 0; v < n; v++)
        {
            if (edge[u][v] > edge[u][k] + edge[k][v])
            {
                edge[u][v] = edge[u][k] + edge[k][v];
            }
        }
    }
}

int main()
{
    // 优化和预处理
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(edge, 0x3f, sizeof(edge));
    const int INF = edge[MAXN - 1][MAXN - 1];
    // 输入和建图
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> t[i];
    for (int i = 0; i < m; i++)
    {
        int u, v, w; cin >> u >> v >> w;
        add_edge(u, v, w);
    }
    // 扫描每条边(题目保证按时间排序,故不必排序)
    int Q, now = 0; cin >> Q;
    while (Q--)
    {
        int x, y, T; cin >> x >> y >> T;
        for (; t[now] <= T && now < n; now++)
        {
            floyd(now);
        }
        if ((t[x] > T || t[y] > T) || edge[x][y] == INF)
        {
            cout<<"-1\n";
        }
        else
        {
            cout<<edge[x][y]<<"\n";
        }
    }
    return 0;
}

朴素Dijkstra算法

思路与实现

Dijkstra算法和SPFA算法是常见的解决最短路问题的两种算法。一般在没有负权、自环的情况下,我们使用常数更小的堆优化的Dijkstra的算法。在堆优化之前,先总结一下朴素Dijkstra算法,时间复杂度为​\(O(n^2)\)。

Dijkstra算法的核心在于贪心的策略。和Floyd的思路类似,我们每次向最短路集合里添加点,最终得到一个最短路树。但在添加新点的策略上有所不同:每次在未确定集合中选择一个离已确定集合的距离最短的点来扩展,直到扩展完毕。

算法大致流程为:

  1. 初始化所有点dis[]为无穷,起点为0;
  2. 从未确定集合(白点)中选取一个距离最短路集合(蓝点)中距离(dis[])最短的点;
  3. 用新加入的点更新其他点的dis[](松弛操作);
  4. 重复2、3直到所有点都被包含在最短路集合中;

核心代码因为几乎不会用到朴素Dijkstra所以就不再写了。大概了解整个算法过程之后就可以直接使用优化过的算法了。

Dijkstra算法 + 堆优化

思路与实现

我们发现,Dijkstra的复杂度来源于寻找最优点和更新最短路两个步骤。我们可以通过合适的树形数据结构来优化寻找最优点的过程来使算法时间复杂度达到\(O(m + nlogn)\)​。最常用的是通过优先队列来优化(大概因为STL中有),当然也有用线段树来优化的方法,就不再赘述。

核心代码:

void dij(int s)
{
    // 优先队列q,其中pair的first存储dis[]作为排序依据
    priority_queue<int, vector<pair<int, int>>, greater<pair<int, int>> q;
    // 初始化
    memset(dis, 0x3f, sizeof(dis)); 
    dis[s] = 0; q.push(make_pair(0, s));
    // 维护过程
    while (q.size())
    {
        int u = q.top().second; q.pop(); // 取出队首
        if (vis[u]) continue; // 已经遍历过
        vis[u] = 1; // 标记
        
        for (int i = head[u]; i; i = edge[i].next) // 前向星遍历
        {
            int v = edge[i].to;
            if (!vis[v] && dis[v] > dis[u] + edge[i].cost) // 松弛操作
            {
                dis[v] = dis[u] + edge[i].cost;
                q.push(make_pair(dis[v], v)); // 入队
            }
        }
    }
}

相关题目

请自行搜索(大雾)。

洛谷P4779 【模板】单源最短路径(标准版)

SPFA算法

思路与实现

SPFA也是一种基于贪心策略的最短路算法。是Bellman-Ford算法(\(O(nm)\)​)的一种优化策略,通过优化之后的平均复杂度是\(O(km)\),其中k为常数。基于试验的平均值是2,也就是在一般情况下要优于Bellman-Ford算法。同时SPFA还具有可以处理负权边,判断自环等特性。

与Dijkstra算法不同,SPFA通过边来更新最短路。每次维护一个待更新的队列,并更新以当前队首的点为起点的边,直到队列为空。

核心代码:

void spfa(int s)
{
    // 初始化
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    queue<int> q; q.push(s); vis[s] = 1;
    // 维护队列
    while (q.size())
    {
        int u = q.front(); // 取出队首
        for (int i = 0; u < edge[u].size(); i++) // 对于每条边
        {
            int v = edge[u][i].to, cost = edge[u][i].cost;
            if (dis[v] > dis[u] + cost) // 松弛操作
            {
                dis[v] = dis[u] + cost;
                if (!vis[v]) // 判断入队
                {
                    vis[v] = 1; q.push(v);
                }
            }
        }
        q.pop(); vis[u] = 0; // 出队(注意位置,防止自环)
    }
}

相关题目

洛谷P1462 通往奥格瑞玛的道路

需要SPFA很多次所以我很喜欢(不)

每次限定最大单边代价来进行SPFA,魔改SPFA + 二分查找的组合。特别的,如果限制最大单边代价为无穷仍无法到达点n,则说明不可能到达奥格玛。

核心代码:

// 分别是原始数据和排序后的数据,分别用来查找指定边的代价和二分查找
long long int fee[MAXN], f_range[MAXN]; 
// @param uplimit 单边代价上限
inline bool spfa(ll uplimit)
{
    // 初始化
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis)); dis[1] = 0;
    queue<ll> q; q.push(1); vis[1] = 1;
    // 维护队列
    while (q.size())
    {
        ll u = q.front();
        for (auto &it : edge[u])
        {
            ll v = it.to, w = it.cost;
            if (dis[v] > dis[u] + w && fee[v] <= uplimit) // 限制单边上限
            {
                dis[v] = dis[u] + w; // 松弛
                if (!vis[v])
                {
                    q.push(v); vis[v] = 1;
                }
            }
        }
        q.pop(); vis[u] = 0;
    }
    if (dis[n] <= hp) // 判断是否成功
    {
        return true;
    }
    else return false;
}
int main()
{
    // 优化和读入
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> hp;
    for (int i = 1; i <= n; i++)
    {
        cin >> fee[i];
        f_range[i] = fee[i];
    }
    for (int i = 1; i <= m; i++)
    {
        int u, v, w; cin >> u >> v >> w;
        add_edge(u, v, w);
    }
    // 特判AFK
    if (!spfa(INF))
    {
        return 0 * puts("AFK");
    }
    // 排序以二分查找
    sort(f_range + 1, f_range + 1 + n, [](ll a, ll b)->bool
    {
        return a < b;
    });
    // 开始二分
    ll l = 1, r = n, mid, ans = 0;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (spfa(f_range[mid]))
        {
            ans = f_range[mid];
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    // 输出
    cout << ans << "\n";
    return 0;
}

SPFA和堆优化Dijkstra的对比

  • 两者都采用贪心的策略;
  • SPFA可以处理负权的情况,Dijkstra不可以;
  • SPFA可以判断环,Dijkstra不可以;
  • SPFA通过边增广,所以在稀疏图快;
  • Dijkstra通过点增广,所以在稠密图上快;

总结

综上,如果不是特别的考察SPFA算法的题目(比如带负权/环或者边权参与问题的题目),建议使用堆优化Dijkstra。因为在极限状态下(如格子图),SPFA的复杂度会严重退化(反复进出队列)从而被毒瘤出题人卡常数。但是因为SPFA也有自己的特性,所以两种算法都需要掌握。

以上,就是冻葱的最短路基础算法小结。感谢观看,时间紧促,难免疏漏,欢迎斧正。

赞赏
本站采用BY-NC-SA-4.0 国际许可协议, 转载请保留出处。
https://dctewi.com/wp-content/uploads/2019/02/head-croped-small-middle-300x300.jpg

冻葱Tewi

文章作者

这个站点的蒟蒻站长~欢迎大家来晃悠!

发表评论

textsms
account_circle
email

  • https://dctewi.com/wp-content/uploads/2019/02/head-croped-small-middle-150x150.jpg

    什么东西都需要自己干的感觉不太好受,所以换回了原来的主题。
    真是快乐,赶紧水了一篇文章。DP的总结一直难产,因为DP真的好深奥啊!Orz
    睡觉睡觉,早睡早起。

    5月前回复

冻葱Tewi

【算法】最短路基础小结
一些基本的最短路算法总结。 内容包括Floyd、Dijkstra、SPFA的原理、应用和对比。附加一些有趣的题目。
扫描二维码继续阅读
2019-05-22
标签云
隐藏
变装