文章

Dijkstra 入门

对于图论中最短路径的三种算法,我们可以总结为以下表格(m为边数,n为点数):

算法 时间复杂度 功能 局限性
Dijkstra O(mlogm) 寻找单源最短路 边权为正
Floyd O(m3) 寻找多源最短路
SPFA O(mn) 寻找单源最短路 边权为负
各最短路算法比较

接下来让我们来康康如何实现Dijkstra算法。

康康就康康

Dijkstra是寻找单源最短路的算法,即指定一个起点的最小值。所以我们需要先规定起点的点的标号为s,而终点的标号为e

接着,我们再设dis[i]表示从s到i的最短路。显然,dis[s]=0,因为起点到自己本身的距离就是0;而我们要求的就是dis[e]

下面,让我们来构造一个真实的例子(注意,Dijkstra可以处理无向图也可以是有向图)。

我们假定从1出发,走到6

显然,对于和1相邻的点,我们可以先推出$dis[1]=0$,$dis[3]=1$,$dis[5]=5$。类似地,对于每一个确定了$dis$的点,都可以继续推出与其相邻的点的$dis$值。

那么根据上面的图,确定了$dis[5]=5$后,$dis[6]=dis[5]+2=7$;确定了dis[3]后,$dis[5]=dis[3]+2=3$……等等,dis[5]的值又被更新了一次。这意味着,如果先推dis[5]的相邻的点的话,其后面的推到都是错误的,因为如果从dis[3]推到dis[5],dis[5]的值仅为3,说明了从1走到5的最小值并不是直接走到5,而是走到3再走到5。由此可见,对于一个已经确定dis的点,应该将其所有相邻的点的期望dis按从小到大排。优先算出期望dis最小的点。于是我们就需要用到优先队列,对于每个相邻的点记录下期望dis值并塞入队列(期望dis值即当前算出的dis值:$dis[next]=dis[now]+val$)。设置优先队列中期望dis值小的在队首,然后从队首一个个取出再塞进新的点即可,有点类似于广度优先搜索。于是$dis[next]=min(dis[next], dis[now]+val)$。这么一来,dis的初始值应全部设为无穷大。但不要忘记vis[s]=0

一处优化

对于上方例子中的点3和点5被更新的问题,在经过改进后,不难发现5会先被点3的距离为3更新,此时一定是最优解。所以我们可以对于dis[now]!=now.val的直接跳过。

#include
   <bits tdc++.h="">

using namespace std;
int n,m,s;
struct node{
    int a,val;
    bool operator < (node b) const{
        return val>b.val;
    }
};
vector
    
      G[100010];
priority_queue
     
       q;
int dis[100010];
int main(){
    cin>>n>>m>>s;
    int a,b,c;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        G[a].push_back({b,c});
    }
    q.push({s,0});
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;
    while(!q.empty()){
        node now=q.top();
        q.pop();
        if(now.val!=dis[now.a])continue;
        for(int i=0;i
      <g[now.a].size();i++){ node="" nxt="G[now.a][i];" if(dis[nxt.a]="">
       dis[now.a]+nxt.val){
                q.push({nxt.a,dis[now.a]+nxt.val});
                dis[nxt.a]=now.val+nxt.val;
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<
       <dis[i]<<" ";="" }="" return="" 0;="" }<="" re="">

        

</dis[i]<<"> </g[now.a].size();i++){>
</bits>
本文由作者按照 CC BY 4.0 进行授权

© Dignite. 保留部分权利。 由  提供CDN加速。

浙ICP备2023032699号 | 使用 Jekyll 主题 Chirpy