首先，我们概括一下大致思想（转载于Korpse——最短路径：Dijkstra算法）
注：Dijkstra算法适用于边权为正的无向和有向图，不适用于有负边权的图！（原因）
用途：
用于求图中指定两点之间的最短路径，或者是指定一点到其它所有点之间的最短路径。实质上是贪心算法。
基本思想：
1.将图上的初始点看作一个集合S，其它点看作另一个集合
2.根据初始点，求出其它点到初始点的距离d[i] （若相邻，则d[i]为边权值；若不相邻，则d[i]为无限大）
3.选取最小的d[i]（记为d[x]），并将此d[i]边对应的点（记为x）加入集合S
（实际上，加入集合的这个点的d[x]值就是它到初始点的最短距离）
4.再根据x，更新跟 x 相邻点 y 的d[y]值：d[y] = min{ d[y], d[x] + 边权值w[x][y] }，因为可能把距离调小，所以这个更新操作叫做松弛操作。
（仔细想想，为啥只更新跟x相邻点的d[y]，而不是更新所有跟集合 s 相邻点的 d 值？ 因为第三步只更新并确定了x点到初始点的最短距离，集合内其它点是之前加入的，也经历过第 4 步，所以与 x 没有相邻的点的 d 值是已经更新过的了，不会受到影响）
5.重复3，4两步，直到目标点也加入了集合，此时目标点所对应的d[i]即为最短路径长度。
（注：重复第三步的时候，应该从所有的d[i]中寻找最小值，而不是只从与x点相邻的点中寻找。想想为什么？）
图解：（动图很快，不容易理解，最好结合上面的步骤自己画一个图，一步一步消化）
原理：这里不进行严格证明，Dijkstra的大致思想就是，根据初始点，挨个的把离初始点最近的点一个一个找到并加入集合，集合中所有的点的d[i]都是该点到初始点最短路径长度，由于后加入的点是根据集合S中的点为基础拓展的，所以也能找到最短路径。
原文链接：https://blog.csdn.net/kprogram/java/article/details/81225176
模板题：https://www.luogu.com.cn/problem/P4779
下面对little_sun的题解进行解释
#include<bits/stdc++.h>//万能头不解释 const int MaxN = 100010, MaxM = 500010;//表示不可改变数值的int常量。 struct edge { int to, dis, next; //to是此边的子节点 //dis是此边的权值 //next是与此边父节点相同的最近的边(的编号) //即为上一条从此边的父节点引出的边(的编号) }; edge e[MaxM]; int head[MaxN], dis[MaxN], cnt; //head数组指：以某点为父节点引出的最新一条边(的编号) bool vis[MaxN]; int n, m, s; inline void add_edge( int u, int v, int d ) { cnt++;//新增一条边，编号要+1 e[cnt].dis = d; e[cnt].to = v;//这条边通向节点v，所以v是此边的一个子节点 e[cnt].next = head[u]; //由于该边是新增的一条边，且父节点是u //那么上一条从u引出的边(的编号，即head[u])就是新增的这条边的next值 head[u] = cnt; //新增的这条边是从u引出的 ，那么这条边(的编号)自然是u的最新一条边 } struct node { int dis;//距离 int pos;//表示从起点到达的点 bool operator <( const node &x )const { return x.dis < dis; } //重载运算符，对node类型的变量以dis为依据排序 //这里重载的小于号 }; std::priority_queue<node> q; //定义优先队列(堆优化，类型是node类型) inline void dijkstra() { dis[s] = 0;//s是起点 //定义从起点到点s的距离是0 q.push( ( node ){0, s} ); //强制类型转换，定义node中的dis=0，pos=s //即定义，这一条边从起点到点s，距离是0 while( !q.empty() )//如果堆不空 { node tmp = q.top();//设置一个node型变量表示堆顶元素 q.pop();//因为已经用tmp存了，可以直接将堆顶元素删掉 int x = tmp.pos, d = tmp.dis; //x表示此边的来源(父节点)，d表示距离(权值) if( vis[x] ) continue; //如果vis[x]被访问过，直接continue vis[x] = 1;//如果没被访问过，标记为已访问 for( int i = head[x]; i; i = e[i].next ) { //i从父节点为x的最新(后)一条边开始遍历 //每次都等于与此边有相同父节点的上一条边，直到没有 //e[i].next就是与正在进行遍历的这条边有相同的父节点的上一条边 //例如节点5先后有1,2,3三条边，那么就从3开始，遍历3,2,1 int y = e[i].to; //定义y是这条边通向的节点 if( dis[y] > dis[x] + e[i].dis ) { //e[i].dis就是从节点x到节点y的各边的权值 //因为在这个循环内我们定义的i就是从x引出的边 dis[y] = dis[x] + e[i].dis; //更新从起点到点y的最小值 if( !vis[y] ) { //如果节点y没被访问过 q.push( ( node ){dis[y], y} ); //定义从起点到节点y的距离是dis[y] } } } } } int main() { scanf( "%d%d%d", &n, &m, &s ); //给定一个n个点，m条有向边的带非负权图，请计算从s出发，到每个点的距离 for(int i = 1; i <= n; ++i)dis[i] = 0x7fffffff; //先把所有边的权值设为无穷大(在这里设为2147483647) for( register int i = 0; i < m; ++i ) { register int u, v, d; //表示从u到v有一条权值为d的有向边 scanf( "%d%d%d", &u, &v, &d ); add_edge( u, v, d ); //新增这条边，并存入e数组 } dijkstra(); //调用函数寻找起点到每点的最小值 for( int i = 1; i <= n; i++ ) printf( "%d ", dis[i] ); //输出 return 0; }