算法竞赛系列 | BFS与优先队列

清华计算机学堂 2023-03-18

474

搜索包括BFS和DFS，这两种算法是算法竞赛的基础。本篇继续介绍BFS的扩展应用，讲解图论的Dijkstra算法。

BFS的代码实现需要用到队列，在不同场景中使用普通队列或优先队列。本篇介绍使用优先队列的经典BFS算法，即一般性的最短路径算法，这种算法实际上是图论的Dijkstra算法。

优先队列

普通队列中的元素是按先后顺序进出队列的，先进先出。在优先队列中，元素被赋予了优先级，每次弹出队列的是具有最高优先级的元素。优先级根据需求来定义，如定义最小值为最高优先级。

优先队列有多种实现方法。最简单的是暴力法，在n个数中扫描最小值，复杂度为O(n)。暴力法不能体现优先队列的优势，优先队列一般用堆实现，插入元素和弹出最高优先级元素，复杂度都为O(log₂n)。虽然基于堆的优先队列很容易手写，不过竞赛中一般不用自己写，而是直接用STL的priority_queue。

用BFS结合优先队列求解一般性最短路径问题

在上一篇中，介绍了边权为1的最短路径的求解。对于边权不等于1的普通图的最短路径问题，可以用BFS结合优先队列求解。

下面介绍“BFS+优先队列”求最短距离的算法步骤。以图3.10为例，起点是A，求A到其他节点的最短路径。图的节点总数为n，边的总数为m。图中边上的数字是边权，边权的实例有长度、费用等。一条路径的总权值等于路径上所有边权的和。

■ 图3.10网络图

基于“BFS+优先队列”的算法用到了贪心策略。从起点A开始，逐层扩展它的邻居，放到优先队列中，并从优先队列中弹出距离A最近的点，就得到了这个点到A的最短距离；当新的点放入队列中时，如果经过这个点，使队列中它的邻居到A更近，就更新这些邻居点到A的距离。

以图3.10为例，步骤如下。

(1) 开始时，把起点A放入优先队列Q中：{A₀}。下标表示从A出发到这个点的路径长度，A到自己的距离为0。

(2) 从队列中弹出最小值，即A，然后扩展A的邻居节点，放入优先队列Q中：{B₆，C₃}。一条路径上包含了多个节点。Q中记录了各节点到起点A的路径长度，其中有一个最短，从优先队列Q能快速取出它。

(3) 从优先队列Q中弹出最小值，即距离起点A最短的节点，这次是C。在这一步，找到了A到C的最短路径长度，C是第1个被确定到起点A的最短路径的节点。考查C的邻居，其中的新邻居D、E直接放入Q：{B₅，D₆，E₇}；队列中的旧邻居B，看经过C到B是否距离更短，如果是就更新，所以B₆更新为B₅，现在A经过C到B，总距离为5。

(4) 继续从优先队列Q中取出距离最短的节点，这次是B，在这一步，找到了A到B的最短路径长度，路径是A-C-B。然后考查B的邻居，B没有新邻居放入Q；B在Q中的旧邻居D，通过B到它也并没有更近，所以不用更新。Q现在为{D₆，E_7}。

继续以上过程，每个节点都会进入Q并弹出，直到Q为空时结束。

在优先队列Q中找最小值，也就是找距离最短的节点，复杂度为O(log₂n)。“BFS+优先队列”求最短路径，算法的总复杂度为O((n+m)log₂n)，即共检查n+m次，每次优先队列复杂度为O(log₂n)。

如果不用优先队列，直接在n个点中找最小值，复杂度为O(n)，总复杂度为O(n²)。

O(n²)是否一定比O((n+m)log₂n)好？下面讨论这个问题。

(1) 稀疏图中，点和边的数量差不多，即n≈m，优先队列的复杂度O((n+m)log₂n)可以写成O(nlog₂n)，它比O(n²)好，是非常好的优化。

(2) 稠密图中，点少于边，即n<m< span="">且n²≈m，优先队列的复杂度O((n+m)log₂n)可以写成O(n²log₂n)，它比O(n²）差。这种情况下，用优先队列反而不如直接用暴力法。

读者如果学过Dijkstra最短路径算法，就会发现，实际上Dijkstra算法就是用优先队列实现的BFS，即Dijkstra+优先队列=BFS+优先队列(队列中存的是从起点到当前点的距离)。

“队列中存的是从起点到当前点的距离”说明了它们的区别，即“Dijkstra+优先队列”和“BFS+优先队列”并不完全相同。例如，如果在BFS时进入优先队列的是“从当前点到终点的距离”，那么就是贪心最优搜索(Greedy Best First Search)，详见下一篇“A*算法”。

根据前面的讨论，Dijkstra 算法也有下面的结论：

(1) 稀疏图，用“Dijkstra+优先队列”，复杂度为O((n+m)log₂n)=O(nlog₂n)；

(2) 稠密图，如果n²≈m，不用优先队列，直接在所有节点中找距离最短的那个点，总复杂度为O(n²)。

提示/

稀疏图的存储用邻接表或链式前向星，稠密图用邻接矩阵。

代码实现

下面用模板题给出Dijkstra算法的模板代码。

● 例3.20最短路径

问题描述： 给出一个图，求点1到其他所有点的最短路径。

输入： 第1行输入n和m，n为点的数量，m为边的数量；第2~m+1行中，每行输入3个整数u，v，w，表示u和v之间存在一条长度为w的单向边。1≤n≤3×10⁵，1≤m≤10⁶，1≤u,v≤n，1≤w≤10⁹。

输出： 共输出n个数，分别表示从1点到1~n点的最短距离，两两之间用空格隔开。如果无法到达则输出-1。

题目中的n很大，路径长度很长，需要用long long型。

题目一般不会要求打印路径，因为可能有多条最短路径，不方便系统测试。如果需要打印出最短路径，代码中给出了打印路径的函数print_path()。

#include<bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;      //这样定义的好处是: INF <= INF+x
const int N = 3e5+2;
struct edge{
int from, to;   //边：起点，终点，权值。起点from并没有用到，e[i]的i就是from
long long w;    //边：权值
    edge(int a, int b,long long c){from=a; to=b; w=c;}
};
vector<edge>e[N];                 //存储图
struct node{
    int id; long long n_dis;          //id：结点；n_dis：这个结点到起点的距离
    node(int b,long long c){id=b; n_dis=c;}
    bool operator < (const node & a) const
    { return n_dis > a.n_dis;}
};
int n,m;
int pre[N];                         //记录前驱结点
void print_path(int s, int t) {       //打印从s到t的最短路
    if(s==t){ printf("%d ", s); return; }     //打印起点
    print_path(s, pre[t]);            //先打印前一个点
    printf("%d ", t);                 //后打印当前点。最后打印的是终点t
}
long long  dis[N];                  //记录所有结点到起点的距离
bool done[N];                   //done[i]=true表示到结点i的最短路径已经找到
void dijkstra(){
    int s = 1;                        //起点s = 1
    for (int i=1;i<=n;i++) {dis[i]=INF; done[i]=false; }    //初始化
    dis[s]=0;                         //起点到自己的距离是0
    priority_queue <node> Q;        //优先队列，存结点信息
    Q.push(node(s, dis[s]));        //起点进队列
    while (!Q.empty())   {
        node u = Q.top();           //pop出距起点s距离最小的结点u
        Q.pop();
        if(done[u.id]) continue;      //丢弃已经找到最短路径的结点。即集合A中的结点            
        done[u.id]= true;
        for (int i=0; i<e[u.id].size(); i++) {  //检查结点u的所有邻居
            edge y = e[u.id][i];       //u.id的第i个邻居是y.to
            if(done[y.to]) continue;   //丢弃已经找到最短路径的邻居结点                
            if (dis[y.to] > y.w + u.n_dis) {
                dis[y.to] = y.w + u.n_dis;
                Q.push(node(y.to, dis[y.to]));    //扩展新邻居，放到优先队列中
                pre[y.to]=u.id;        //如果有需要，记录路径
            }
        }
    }
    // print_path(s,n);                如果有需要，打印路径: 起点1，终点n
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)   e[i].clear();
    while (m--) {
        int u,v,w;   scanf("%d%d%lld",&u,&v,&w);
        e[u].push_back(edge(u,v,w));
     // e[v].push_back(edge(v,u,w));     本题是单向边
    }
    dijkstra();
    for(int i=1;i<=n;i++){
        if(dis[i]>=INF)  cout<<"-1 ";
        else   printf("%lld ", dis[i]);
    }
}