Dijkstra算法使用于跑最短路的算法。
算法思想
假定图是不带负权的有向图或无向图，采用贪心策略，每次扩展一个距离为最短的点，在以这个点为中间点，更新其他的所有点的距离。当所有边权都为正时，由于不会存在一个距离更短的没有扩展过的点，所以以这个点的距离永远不会再被更新，因而保证了算法的正确性。
算法流程
- 初始化dist[1] = 0，其余的点时无穷大。
- 找出一个未被标记的、dist[u]最小的节点u，然后标记节点u。
- 扫描节点u的所有出边，若有dist[v] > dist[u] + w[i]（v是到达的节点，w是边权），则使用dist[u] + w[i]更新dist[y]。
- 重复上述的两个步骤直到所有点都被标记。
算法优化
在上述算法过程我们可以在O（n*m）的时间内算出答案，主要问题在于找出节点u，我们可以利用堆对dist数组进行维护从而使获得最大值的时间从O（n）变为O（1），但是在维护过程中我们仍然需要O（log（n））的时间来维护。所以我们可在O（mlog（n））的时间内完成最短路。
值得注意的是，在我们每次更新的时候，优先队列不支持更改操作，即我们每次更改dist实际上是加入了一个新的节点去维护dist，所以，我们在调取到之前的dist时要选择直接跳过，否则会直接TLE飞起来。
算法模板（洛谷P4779）
#include<bits/stdc++.h> using namespace std; int head[100001],ne[200001],to[200001],w[200001],edgenum=0; int dis[100001]; bool vis[100001]; int inf; struct node{ int pos,val; bool operator <(const node &a)const {return a.val<val;} }; priority_queue<node> que; inline void addedge(int f,int t,int co) { ne[++edgenum]=head[f]; head[f]=edgenum; to[edgenum]=t; w[edgenum]=co; } inline int read() { int x = 0, w = 0; char ch = getchar(); for(;!isdigit(ch);w |= (ch == '-'), ch = getchar()); for(;isdigit(ch);x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar()); return w ? -x : x; } inline node make_node(int x, int y) { node a; a.pos = x, a.val = y; return a; } void Dijkstra(int s) { memset(dis,0x3f,sizeof(dis)); // inf = dis[0]; dis[s]=0; que.push(make_node(s, dis[s])); while(!que.empty()) { node x=que.top();que.pop(); int u = x.pos; if(x.val > dis[u]) continue; //这一步就相当于是删除了那些不够优的节点 vis[u]=true; for(int i=head[u];i;i=ne[i]) { int v=to[i]; if(vis[v]) continue; if(dis[v]>w[i]+dis[u]) { dis[v]=w[i] + dis[u]; que.push(make_node(v, dis[v])); } } } } int main() { int n = read(),m = read(),s = read(),x,y,l; for(int i=1;i<=m;i++) { //scanf("%d%d%d",&x,&y,&l); x = read(), y = read(), l = read(); addedge(x,y,l); } Dijkstra(s); for(int i=1;i<=n;i++) printf("%d ",dis[i]); printf(" "); return 0; }