单源最短路算法，不能处理负环，朴素版时间复杂度\(O(n^2)\)，堆优化版时间复杂度\(O(nlogn)\)。
Dijkstra算法的流程是：
将所有的节点分为A、B的两个集合，一开始A集合中只有起点，其他的节点在B集合。定义B中的节点与A的距离：若邻接A中的结点，则距离为边权；反之距离无穷大。
1.找到与A距离最小的B集合中的节点，称之为d。（朴素版需要遍历B集合，堆优化版直接得到）
2.将d加入集合A，并在集合B中删去d。
3.更新B到A的距离。（只需更新d在B中的邻接节点）
4.若B集合为空，则退出；反之回到步骤1。
模板题目练习：洛谷：P4779
代码示例：（用优先队列实现的堆优化版）
#include <bits/stdc++.h>const int maxN = 100005, maxM = 500005;struct edge
{int to, dis, next;
};
edge eg[maxM];int head[maxN], dis[maxN], cnt;
bool vis[maxN];
int n, m, s;inline void add_edge(int u, int v, int d)
{cnt++;eg[cnt].dis = d;eg[cnt].to = v;eg[cnt].next = head[u];head[u] = cnt;
}struct node
{int dis;int pos;bool operator<(const node& x) const{return x.dis < dis;}
};std::priority_queue<node> nd;void dijkstra()
{dis[s] = 0;nd.push(node({ 0, s }));while (!nd.empty()){node tmp = nd.top();nd.pop();int x = tmp.pos, d = tmp.dis;if (vis[x])continue;vis[x] = true;for (int i = head[x]; i; i = eg[i].next){int y = eg[i].to;if (dis[y] > dis[x] + eg[i].dis){dis[y] = dis[x] + eg[i].dis;if (!vis[y]){nd.push(node({ dis[y], y }));}}}}
}
