[算法笔记] Dijkstra

· · 题解

updated. 2019.11.3

Dijkstra是用于求解正权图上的单源最短路径(SSSP)问题的算法

在这里我也想说一下关于SPFA和Dij Dij是一个求没有负权边的图的单源最短路的算法 SPFA是一个求存在负权边的图的单源最短路以及判负环的算法 看似一字之差 写起来也很像 但其实Dij和SPFA完全是不同的思想 Dij是贪心思想 利用了一个只有没有负权边的图才拥有的性质 而SPFA更像是一个"暴力"算法

另外 SPFA没死
下面是正文

算法流程

Dijkstra算法其实是一个基于贪心的过程
正确性会在后面提及

设起点是s

$vis_u$表示$u$点的最短路是否已经被确定 $1.$初始化起点的距离$dis_s$为0 其它节点都是正无穷 $2.$找到所有未确定最短路的点中 与起点的距离$dis_u$最小的点$u $4.$扫描$u$的所有出边 如果$s\to u\to v$这条路径更优(即$dis_u+w(u,v)<dis_v$) 就把$dis_v$更新为$dis_u+w(u,v) 这里放张图理解 代码在后面 之前画的图太丑了 所以自己手画了一幅 蓝点表示已经确定了最短路 打$\sqrt{}$的代表按距离的小根堆的堆顶 ![](https://s2.ax1x.com/2019/11/03/KORp1e.jpg) ~~最后放一张动图~~ 动图炸了 所以点[这里](https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html)吧/kk ## 正确性 Dijkstra是基于贪心思想实现的 在每一轮更新后 还未访问到过的节点一定不优于已经访问到过的节点 而在已经访问到过的节点中 找出未确定最短路且当前$dis_u$最小的$u

由于其它点的dis本来就已经比dis_u大 边权还是非负数 它们不可能更新dis_u 所以dis_u已经被确定了 u的最短路就确定了 这样一步一步下来可以确定所有点的最短路

优化

寻找全局最小值这一步是可以优化的

加入元素、查找最小值、删除最小值
用堆来实现这些操作非常合适

所以就有了堆优化的Dijkstra
堆中每个元素存两个值 结点编号x和入堆是该点被更新成的距离dis

主要思想不变 每次找距离最小点是直接取出堆顶并删除堆顶 更新最短路的时候 将更新后的节点入堆 注意一个点可能会被更新多次而入堆多次 但是只有**最后一次入堆才是正确的dis** 同时**也一定是在所有入堆操作结束后才会出堆** 所以直接开个数组判断有没有出堆过就好了 当然也可以根据堆中元素的距离大小和点的最短路大小直接判断 直接给出堆优化Dijkstra代码: ```cpp struct node{ LL dis,x; bool operator < (const node &nd)const{ return nd.dis < dis; } // 重载运算符 注意pq的重载是反的 }h; priority_queue <node> q; // 这叫堆 void add_edge(int f,int t,int C){ ++ ec; to[ec] = t; cst[ec] = C; nxt[ec] = hed[f]; hed[f] = ec; } void dijkstra(){ memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[s] = 0; h.x = s; h.dis = 0; q.push(h); while(!q.empty()){ h = q.top(); q.pop(); int u = h.x,v; if(vis[u]) continue; vis[u] = 1; for(int i = hed[u];i;i = nxt[i]){ v = to[i]; if(dis[v] > dis[u] + cst[i]){ dis[v] = dis[u] + cst[i]; if(!vis[v]){ h.x = v; h.dis = dis[v]; q.push(h); } } } } for(int i = 1;i <= n;i ++) printf("%d ",dis[i]); } int main(){ scanf("%d %d %d",&n,&m,&s); while(m --){ scanf("%d %d %d",&a,&b,&c); add_edge(a,b,c); } dijkstra(); return 0; } ``` ### 时间复杂度证明: 由于每一个点只会出堆一次(严格来说是只扩展这个节点一次) 所以每一个点和每一条边都只会访问一次 堆优化Dijkstra的时间复杂度为$O((N+M)logM)

另外 如果图中存在负权边 即使没有负环 Dijkstra 也会有错误
如果不用新数组判断而用距离dis来判断一个点是否入堆过 那么会被卡成指数级复杂度

简单应用

在求最短路的过程中可以同时维护一些其他信息
这些信息也应该能够传递
1.记录路径
每次更新最短路的时候记一个pre即可 代表这条路径是由哪个点过来的
最后直接从最后一个点不断取pre 输出路径 

void dijkstra(){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s] = 0; t.x = s; t.dis = 0; q.push(t);
    while(!q.empty()){
        h = q.top(); q.pop();
        int u = h.x,v;
        if(vis[u]) continue; vis[u] = 1;
        for(int i = hed[u];i;i = nxt[i]){
            v = to[i];
            if(dis[v] > dis[u] + cst[i]){
                dis[v] = dis[u] + cst[i];
           pre[v] = u;
                t.x = v; t.dis = dis[v];
                q.push(t);
            }
        }
    }
}
while(now){
    printf("%d ",now);
   now = pre[now];
}

2.最短路计数
记录一个cnt_u代表起点到u的最短路有多少条
在dis_v=dis_u+w(u,v)时 加上来自u的方案数 

void dijkstra(int s){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    dis[s] = 0; cnt[s] = 1; t.x = s; t.dis = 0; q.push(t);
    while(!q.empty()){
        h = q.top(); q.pop();
        int u = h.x; if(vis[u]) continue; vis[u] = 1;
        for(int i = hed[u];i;i = nxt[i]){
            int v = to[i];
            if(dis[v] > dis[u] + w[i]){
                dis[v] = dis[u] + w[i]; cnt[v] = cnt[u];
                t.x = v; t.dis = dis[v];
                q.push(t);
            }
            else if(dis[v] == dis[u] + w[i]){
                cnt[v] += cnt[u];
                cnt[v] %= N;
            }
        }
    }
}

3.次短路
记录到每个点的最短路和次短路
这里由于边能够重复走 就不能够使用是否出过堆判断 一个点可能要更新其它点多次
这里只要用路程判断 就是堆中元素\{x,dis\}的dis比次短路dis2_x还大 就抛弃这个元素 取下一个

还有一种神奇的解法 把每一条边再加一条边 起点终点相同 边权为原来的三倍 代表u\to v\to u\to v 

void dijkstra(int fr){
    memset(dis,0x3f,sizeof(dis)); dis[fr] = 0;
    memset(ds2,0x3f,sizeof(ds2));
    memset(vis,0,sizeof(vis));
    priority_queue <node> q;
    t.x = fr; t.dis = 0; q.push(t);
    while(!q.empty()){
        h = q.top(); q.pop();
        int u = h.x; if(vis[u]) continue; vis[u] = 1;
        for(int i = hed[u];i;i = nxt[i]){
            int v = to[i];
            if(dis[v] > dis[u] + w[i]){
                ds2[v] = dis[v];
                dis[v] = dis[u] + w[i];
                t.x = v; t.dis = dis[v];
                q.push(t);
            }
            else if(ds2[v] > dis[u] + w[i] && dis[v] != dis[u] + w[i]) ds2[v] = dis[u] + w[i];
            if(ds2[v] > ds2[u] + w[i]) ds2[v] = ds2[u] + w[i];
        }
    }
}
for(int i = 1;i <= m;i ++){
    scanf("%d %d %d",&a,&b,&c);
    add_edge(a,b,c);
    add_edge(b,a,c);
    add_edge(a,b,3 * c);
    add_edge(b,a,3 * c);
}