最短路径问题

· 浏览次数 : 0

小编点评

最短路径问题是最基本的图论问题之一,本章将介绍几种常见的最短路径算法及其应用。 一、Flord算法 Flord算法是一种简单而有效的最短路径算法,它通过动态规划求解最短路径。算法的核心思想是尝试从其他所有点借道来缩短路径,状态转移方程为:dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j])。Flord算法的时间复杂度为O(n^3),但对于小图上的最短路问题,它是一个优秀的选择。 二、Djikstra算法 Djikstra算法是基于BFS的贪心算法,它通过扩展最短路径来求解最短路径问题。算法的主要思想是将起点加入到优先队列中,并不断选取距离起点最近的点进行处理。Djikstra算法的时间复杂度为O((m+n)log_2n),对于小图上的最短路问题,它是一个高效且稳定的选择。 三、Bellman-ford算法 Bellman-ford算法是一种简单的单元最短路算法,它通过多次推出来松弛各点的最短距离。算法的时间复杂度为O(mn),能够处理负边权问题。然而,当图的顶点数和边数很大时,Bellman-ford算法的效率会变得非常低。在实际应用中,通常使用SPFA算法来处理大规模图的最短路问题。 四、SPFA算法 SPFA算法是Bellman-ford算法的队列优化版,它通过维护变化点的邻接列表来优化算法的运行时间。SPFA算法的时间复杂度为O(mn),最差情况下可能会达到O(mn)。尽管SPFA算法在某些情况下可能不如Djikstra算法稳定,但它仍然是一个处理大规模图最短路问题的有效工具。 总结:本章介绍了四种常见的最短路径算法,包括Flord、Djikstra、Bellman-ford和SPFA。每种算法都有其适用场景和优缺点。在实际应用中,需要根据问题的具体需求选择合适的算法。

正文

最短路径问题

最短路问题是图论中一种重要的算法,本章将包括:

一.概念

1.概念

一张图中n条点和m条边,边都有权值,权值可正可负。边可能有向,可能无向,给定起点s和终点t,在所有能链接s和t的路径中,寻找所经权值最小的路径,此为最短路径问题。

2.解决方案

最容易想到的方法是暴力法,枚举所有路径,再进行大小比较,但明显不可行,一定会超时。

更好的方法即为在寻路的过程中,动态规划将要走的最短路径,此也为下文的算法思路和方法。

二. \(Flord\) 算法

\(Flord\) 算法是最简单的最短路径算法,甚至短于暴力搜索。

1.算法思想

\(i\)\(j\) 的最短路径,对于其他所有点,每个点 \(k\) 都尝试一遍能否 \(i\) 借道 \(k\)\(j\) 会不会更短。

对于这样的思路,我们可以用动态规划来解决,定义 \(dp[k][i][j]\) ,表示 \(k\) 阶段 \(i\)\(j\) 的最短路,不难发现 \(dp[k][i][j]\) 是由 \(dp[k-1][i][j]\) 推出,1.若不变,则直接继承。2.若变,则是其加借道的权值即可。由是,我们便可推出其状态转移方程:

\[dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j]) \]

由状态转移方程可知, \(dp[k][i][j]\) 的值只与 \(dp[k-1][i][j]\) 有关,由是,我们可利用滚动数组将 \(dp\) 数组降维,来到二维,得到新的状态转移方程:

\[dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]) \]

综上,可得出 \(Flord\) 算法的核心代码。

2.代码详解

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

由于使用了滚动数组,所以 \(k\) 循环必须在 \(i\)\(j\) 循环之外。

3.算法应用及局限性

对于 \(Flord\) 算法来说,其能一次跑出所有点对之间的最短路,我们称这种求所有点对之间的最短路的问题为多源最短路问题,对比其他算法来说,解决多源最短路问题, \(Flord\) 算法 \(O(n^3)\) 的均摊复杂度是最优秀的。

当然,对于求一组点对之间的最短路的单源最短路问题, \(Flord\) 算法 \(O(n^3)\) 的复杂度便难以接受。

综上, \(Flord\) 算法适合解决 \((n<300)\) 的小图上的最短路问题。

二. \(Djikstra\) 算法

\(Djikstra\) 算法基于 \(BFS\) 可以说“ \(Djikstra\) = \(BFS\) +贪心”

1.算法思想

对于 \(Djikstra\) 算法来说,主要为点之间的扩展,对于我们将要处理的点来说,我们将其所有邻居加入优先队列中。再在优先队列中选择最小(队首的)的那条边进行处理,优先队列中存放的是各点到起点的距离。

经过手动模拟,可以得出,若一个点 \(A\) 在之前的处理中已确定到起点的最小值,则后续的处理与其无关,即对于一个点,若其已被确定,则其不会再入队。

2.代码详解

void dijkstra(int s){             //s为起点
    for(int i=1;i<=n;i++){dis[i]=inf;done[i]=false;}
    //初始化,dis[i]表示i点到起点的距离,done[i]表示i点已确定。
    dis[s]=0;            //起点到自己的距离为0
    priority<node>q;     //优先队列,小根堆
    q.push(node(s,0));
    while(!q.empty()){
        node u=q.top();             //弹出距离最小的点
        q.pop();
        if(done[u.id]) continue;    //若此点已确定
        done[u.id]=true;
        for(int i=0;i<=e[u.id].size();i++){
            edge y=e[u.id][i];
            if(done[u.to]) continue;
            if(dis[v.to]>y.w+u.dis){  //若通过此点更短
                dis[y.to]=y.w+u.dis;
                q.push(node(y.to,dis[y.to]));
            }
        }
    }
}

3.算法特征及其局限性

\(Djikstra\) 算法是较为高效,稳定的最短路径算法,每次得出一条最短路径,所以稳定,每次只更新一个点,所以高效。

当然, \(Djikstra\) 算法也并非完美无缺,其也有其局限性,那就是对于其将要处理的图来说,其不能出现权值为负的情况,若有负边权,则贪心不成立,即不能保证“全局最优解由局部最优解组成”的最优性定理,导致 \(Djikstra\) 算法出现错误。

三. \(Bellman-ford\) 算法

\(Bellman-ford\) 算法是一种简单的单元最短路算法。

1.算法思路

我们通过多次推出,来松弛(指修改到各点的最短距离)各点的最短距离,也就是说通过一步步地推出最远的点的最近路径。

对于我们进行的每一次松弛来说,对每一条线段进行遍历,看线段端点经过此线段能否比之前距起点的距离更近,若是,则更新。由于考虑回退边的存在,所以共进行 \(n\) 次操作。

2.代码详解

\(Bellman-ford\) 算法的主代码较少:

for(int k=1;k<=n;k++)
    for(int i=1;i<=m;i++)
        if(dis[v[i]]>dis[u[i]]+w[i])
            dis[v[i]]=dis[u[i]]+w[i]

注:保证在主代码之前初始化 \(dis\) 数组,除 \(dis[s]\) 之外,全部初始化为 \(INF\)

3.算法特性

由算法思路得, \(Bellman-ford\) 算法遍历 \(n\) 条边 \(m\) 条边,其复杂度为 \(O(mn)\) ,虽然其能处理 \(Djikstra\) 处理不了的负边权问题,但当 \(n\)\(m\) 都很大时, \(Bellman-ford\) 算法的效率将会十分糟糕,不过这也引出了我们的的第四种算法 \(SPFA\)

四. \(SPFA\) 算法

\(SPFA\) 算法基于 \(Bellman-ford\) 算法的队列优化版。

1.算法思想

既然其是 \(Bellman-ford\) 算法的优化,那么基本的思想不会改变,我们需要找到如何优化 \(Bellman-ford\) ,对于 \(Bellman-ford\) 的每一次松弛来说,我们需要遍历每一条边,其实并没有必要,对于一个其邻居已经确定的点来说,重复遍历它的每条边是无意义的,我们只需对发生变化的点的邻居进行维护即可,队列完全适合,于是这便是 \(SPFA\) 算法。

2.代码详解

bool inq[maxn];              //inq[i]表示i已在队列中
void spfa(int s){            //s为起点
    for(int i=1;i<=n;i++){dis[i]=inf;inq[i]=false;}  //dis[i]为i到起点的距离
    dis[s]=0;
    queue<int>q;
    q.push(s);
    inq[s]=true;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        inq[u]=false;
        for(int i=0;i<e[u].size();i++){
            int v=e[u][i].to,w=e[u][i].w;
            if(dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                if(!inq[v]){                //若v不在队列中
                    inq[v]=true;
                    q.push(v);              //入队
                }
            }
        }
    }
}

3.特征及性质

\(SPFA\) 算法节点的入队数量决定了 \(SPFA\) 算法的效率,由于不能确定重新入队的节点数量,所以 \(SPFA\) 不稳定,最差情况下为 \(O(mn)\) ,此时我们便应选择稳定的 \(Djikstra\) 算法来解决问题。

当给定的图如下图时:

\(SPFA\) 的复杂度将十分糟糕,不如 \(Djikstra\) 。当然, \(SPFA\) 也有自己的优点,即允许负边权的存在。其也可用来判断负环。

五.总结

这四种算法各有千秋。

问题 边权 算法 复杂度
非负数 \(Djikstra\) \(O((m+n)log_2n)\)
单源最短路 允许有负数 \(Bellman-ford\) \(<O(mn)\)
允许有负数 \(SPFA\) \(O(mn)\)
多远最短路 允许有负数 \(Flord\) \(O(n^3)\)

其中,求多源最短路,则使用 \(Flord\) ,若求单源最短路且无负边权,则推荐使用稳定的 \(Djikstra\) 。若有负边权,则使用 \(SPFA\)\(Bellman-ford\) 的应用场景很少,一般不会用到,可用来做小图的小码量选择。

与最短路径问题相似的内容:

最短路径问题

最短路径问题 最短路问题是图论中一种重要的算法,本章将包括: 目录最短路径问题一.概念1.概念2.解决方案二. \(Flord\) 算法1.算法思想2.代码详解3.算法应用及局限性二. \(Djikstra\) 算法1.算法思想2.代码详解3.算法特征及其局限性三. \(Bellman-ford\)

使用队列解决迷宫问题(广度优先搜索 / 最短路径)

博客地址:https://www.cnblogs.com/zylyehuo/ # -*- coding: utf-8 -*- from collections import deque maze = [ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 1, 0,

二叉树的最小深度问题

二叉树的最小深度问题 作者:Grey 原文地址: 博客园:二叉树的最小深度问题 CSDN:二叉树的最小深度问题 题目描述 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明:叶子节点是指没有子节点的节点。 题目链接见:LeetCode 111. Mini

Solution -「LOJ #3310」丁香之路

首先有两个前置技巧:1) 两点间的最短距离就是直接连接两点的边的长度;2) 遍历一个子图的最小花费是最小生成树的边权之和乘二。原问题让我们找出一条最短且必经过钦定边的 \(( s, i )\) 路径,那么我们先将 \(\lang s , i \rang\) 连上,问题就变成了找出一条最短且必经过钦定

最短路三种算法详解

# 最短路 最短路问题即,给你一张图,让你求出图中两点的最短距离。 这篇文章会讲解 $Dijkstra$、$Spfa$、$Floyd$ 三种算法,让您透彻理解最短路! ## Dijkstra ### 朴素版 题目: ![image](https://img2023.cnblogs.com/blog/

LeetCode 周赛 346(2023/05/21)仅 68 人 AK 的最短路问题

> **本文已收录到 [AndroidFamily](https://github.com/pengxurui/AndroidFamily),技术和职场问题,请关注公众号 [彭旭锐] 提问。** - [LeetCode 单周赛第 345 场 · 体验一题多解的算法之美](https://mp.wei

LeetCode 周赛 347(2023/05/28)二维空间上的 LIS 最长递增子序列问题

> **本文已收录到 [AndroidFamily](https://github.com/pengxurui/AndroidFamily),技术和职场问题,请关注公众号 [彭旭锐] 提问。** - 往期回顾:[LeetCode 单周赛第 346 场 · 仅 68 人 AK 的最短路问题](http

LeetCode 周赛 340,质数 / 前缀和 / 极大化最小值 / 最短路 / 平衡二叉树

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 上周跟大家讲到小彭文章风格的问题,和一些朋友聊过以后,至少在算法题解方面确定了小彭的风格。虽然竞赛算法题的文章受众非常小,但却有很多像我一样的初学者,他们有兴趣参加但容易被题目难度和大神选

Johnson 全源最短路

Johnson 全源最短路 Johnson 和 Floyd 一样是能求出无负环图上任意两点间最短路径的算法。 引入 求任意两点间的最短路可以通过枚举起点,跑 \(n\) 次 SPFA 来解决,时间复杂度是 \(O(n^2 m)\) 的,也可以用 Floyd 解决,复杂度为 \(O(n^3)\)。 或

leetcode 二叉树的最小深度

给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明:叶子节点是指没有子节点的节点。 示例 1: 输入:root = [3,9,20,null,null,15,7] 输出:2 示例 2: 输入:root = [2,null,3,null,4,null,5,