何为Dijkstra
单源最短路，即从一个点出发，到其他所有点的最短距离，起点可以是任意一点
Dijkstra的本质是贪心
过程
在这张图中，如果我们要$1$号点位起点$st$，求最短路的过程大概是这样的
定义一个d数组，其中$d[i]$代表从起点$st$到$i$的最短距离，首先认为$st$到所有点的距离都是$inf$，也就是我们要做的初始化
初始化之后就变成了这样
从当前点出发，找所有和它邻接的点，看能否用这条边更新最短路的长度
先从$1$号点出发更新$2$号点，我们发现$0+1<inf$，于是我们欣然接受这个方案，将$2$号点的距离更新成$1$，也就是这样
同理我们也可以更新$3$号点的距离
更新完$3$号点后，$1$号点的所有邻接点全部更新完毕，也可以说$1$号点的使命结束，可以删掉了
此时这张图就变成了这样
然后我们再选择一个和原点距离最近的点（也就是$2$号点）进行更新
和上面同理，我们可以对$3$号点和$4$号点进行更新
我们并不需要关心具体需要怎样走，我们只关心从$2$号点到$4$号点时$1+2<inf$以及$2$号点到$3$号点时$1+2<4$，新的距离比原来的距离短，我们就进行更新
此时$2$号点使命结束，删除
我们注意到$3$和$4$到原点的距离相同，此时随便选一个进行拓展即可
拓展$5$号点同理
拓展完的图就变成了这样
此时我们再看这句话，相信你就能够理解
Dijkstra的本质是贪心
其中，贪心体现为每次都找最近点进行拓展，可以保证每次开始拓展时，这个点到原点的距离一定是最小的
此处可以进行反证：
如果这个点的距离不是最小的，就一定能找到另一个点离$st$更近来进行拓展
简单总结一下
Dijkstra的过程大概可以分为这样几步：
-
初始化$d$数组
-
找出距离最小的点$u$
-
遍历$u$的所有出边，并进行更新
还没懂的话可以看看这里
朴素版代码
ll d[N];//d[i]为原点到点i的最短距离
void dijkstra(int x)//x是原点
{
memset(d, 0x3f, sizeof(ll) * (n + 1));
d[x] = 0;//自己到自己的距离为0
bitset<N> vis;//true表示已经拓展过
for(int i = 1; i <= n - 1; ++ i)
{
//找出最小点(距离源点最近的点)
int u = 1;
for(int j = 1; j <= n; ++ j)
if(vis[u] || (!vis[j] && d[j] < d[u]))u = j;
vis[u] = true;//表示u已经拓展过
//此时d[u]已为最优
for(const auto &[v, w] : g[u])
if(!vis[v] && d[v] > d[u] + w)d[v] = d[u] + w;
}
}
上面这段代码的时间复杂度为$O(n2)$，能够计算的$n$的范围大约是$104$以内，在大多数情况下并不能过题，所以我们就需要对一些步骤进行优化
很明显，初始化和遍历所有出边这两步并没有什么方案可以优化，我们便把目光放在第二步
优化
插入元素，查询最小值，删除最小值
这几步操作很容易让我们想到堆，也就是优先队列
我们可以用距离为第一关键字进行比较，并存入一个小根堆，这样我们查询最小值时就可以优化到$log$级别
堆优化代码
struct node
{
ll x, w;//x表示出点 w表示权值
bool operator < (const node &v)const//按照w小的优先
{
return w == v.w ? x < v.x : w > v.w;
}
};
vector<node> g[N];
ll d[N];
int n, m;
void dijkstra(int x)
{
memset(d, 0x3f, sizeof(ll) * (n + 1));
d[x] = 0;//初始化起点
bitset<N> vis;//表示已经拓展过
priority_queue<node> pq;//定义了一个大根堆，但是重载运算符时进行了反转，也就是堆顶元素的距离最小
pq.push({x, d[x]});//将起点作为拓展点
while(!pq.empty())
{
int x = pq.top().x;pq.pop();//取出距离最小的元素
if(vis[x])continue;//跳过冗余的拓展点
vis[x] = true;//取出的x点已经得到了最短距离d[x]
for(const auto &[y, w] : g[x])
{
if(!vis[y] && d[y] > d[x] + w)//如果vis[y]，说明y已经得到了最短距离，无需更新
{
d[y] = d[x] + w;
pq.push({y, d[y]});
}
}
}
}