前言：

某蒟蒻学习DIjkstra的笔记？emm……

（上网课划的水，就是现在补课眼里的泪）

废话不多说，开始正文吧

正文：

作为一个资深蒟蒻，目前还不会SPFA,（扯远了，咳咳…）

1.定义

Q：Dijkstra算法是什么？

A：专业一点就是：

通俗一点：上面的还不够通俗？ “最短路” 你细品，多品两遍就懂了。

2.思路

一般两种，一种为暴力Dij，显然比较慢，时间复杂度为O（n^2），本蒟蒻也是先学的这个，另一种用堆优化，目前感觉比较神奇，

PS：堆优化，顾名思义，就是用堆进行优化。我们通过学习朴素DIJ算法，明白DIJ算法的实现需要从头到尾扫一遍点找出最小的点然后进行松弛。这个扫描操作就是坑害朴素DIJ算法时间复杂度的罪魁祸首。所以我们使用小根堆，用优先队列来维护这个“最小的点”。从而大大减少DIJ算法的时间复杂度。

（1）朴素算法

先说朴素算法，毕竟比较熟悉：

用st记录起点，dis[i]数组记录最短路径，也就是起点到i的最小权值和（本蒟蒻这么理解的），vis数组打标记；

首先邻接表存图，这个难理解，其实就是连边，不理解背过也没有问题，不在本文范围内，给出代码：

void add(int u,int v,int w) {
    e[++tot].v=v;
    e[tot].w=w;
    e[tot].nxt=head[u];
    head[u]=tot;
}//这样就可以把边连起来了。

首先把dis数组都赋为极大值INF，表示两点间没有联通，vis数组都赋为零，表示没有遍历：

（对于INF怎么赋为极大值，令INF=0x7ffffff即可，前面看似乱码，实际上是表示极大值）

for(re int i=1; i<=n; i++) dis[i]=INF,vis[i]=0;//re为优化，打不打没有影响

接下来处理与起点st相邻的点，想想dis数组是干嘛的，所以：

for(re int i=head[st]; i; i=e[i].nxt) dis[e[i].v]=e[i].w;//就可以把dis[i]赋值为与st相连边i的权值了。

因为要处理后面的路径，所以要把起始位置也就是dis[st]赋为零，为什么？往后看就明白了，再设now记录当前位置；

然后开始枚举n个点，如何枚举，当所有vis的值都改变就退出枚举，

while(vis[now]==0)//可以实现了

当然你枚举到这个点，那就把这个点的vis标记为1，再设一个Min，目的是找下个最小权值的位置（这样理解应该没问题）；

然后呢？枚举与now相邻的点呗，和上面差不多

for(re int i=head[now],w,v;i;i=e[i].nxt)

令w为相连边的权值，v为下条边；

如何更新？

v=e[i].v;
w=e[i].w;
if(!vis[v]&&dis[v]>dis[now]+w){
      dis[v]=dis[now]+w;
}

很明显在第一次操作时，dis[v]没有被操作过所以值为INF，然后铁定是大于后面的，然后就把与now连的边更新完了。

既然都连完了，那就找最小的那个，怎么找？

for(re int i=1;i<=n;i++){ //枚举n个点
            if(!vis[i]&&dis[i]<Min){ //如果vis==0（说明不是计算过的点）并且dis[i]<Min,(就是前面的Min，发挥作用了吧)
                Min=dis[i];
                now=i;
            }
      }

 

然后？？？

然后就没了！核心就这些，附上完整代码：

void dij(int st){
    for(re int i=1;i<=n;i++) vis[i]=0,dis[i]=INF;
    for(re int i=head[st];i;i=e[i].nxt) dis[e[i].v]=e[i].w;
    dis[st]=0,now=st;
    while(vis[now]==0){
        vis[now]=1,minn=INF;
        for(re int i=head[now],w,v;i;i=e[i].nxt){
            v=e[i].v;
            w=e[i].w;
            if(!vis[v]&&dis[v]>dis[now]+w){
                dis[v]=dis[now]+w;
            }
        }
        for(re int i=1;i<=n;i++){
            if(!vis[i]&&dis[i]<minn){
                minn=dis[i];
                now=i;
            }
        }
    }
}

（2）堆优化

啊这，本蒟蒻还在学习中，等本蒟蒻心领神会了再说吧（其实就是菜），我会抓紧学习，不当鸽子精（新中国之后不允许动物成精…）

后记：

光说不练假把式，还是要多刷题。

（第一篇笔记啊啊啊，很nice，哪里不明白私信我再改）

祝OI学习愉快

UPD：2021.8.25