单源最短路问题
给定一张 (n) 个点的有向图，边权均为正数。给定起点 (st) ，要求出 (st) 到其他所有点的最短路。
算法简介
( ext{Dijkstra}) 算法是典型的单源最短路径算法，朴素算法的时间复杂度为 (O(n^2)) ，加上堆优化后可以达到 (O((n+m)log n)) 的时间复杂度，并且在实际应用中较为稳定，需要在各种题目中灵活应用！
算法流程
( ext{Dijkstra}) 算法的主要思想是贪心，但它只适用于不含负权边的图。
它的主要思想是：以起始点为中心向外层层扩展，直到扩展到终点为止。
- 初始化
设 (d[i]) 表示起点 (st) 到 (i) 点的最短距离，并把初始值为无穷大 (+∞) ， (d[st]=0) 。把点集 (V) 分成两部分：已经确定最短路的点集 (S) 与未确定最短路的点集。我们先将 (S) 初始化为空集。
- 具体过程
先找到一个不在 (S) 中 (d) 值最小的点 (u) ，然后将它加入到 (S) 中。
再扫描节点 (u) 所有出边 ((u,v,w)) ，对所有 (v) 做一次松弛操作，即若 (d[v]>d[u]+w) ，则用 (d[u]+w) 更新(d[v])。
重复上述步骤，直到所有节点被加入到 (S) 中。
正确性的简要证明
我们知道，当所有边长都是非负数的时候，全局最小值不可能再被其他节点更新。即在第 (2) 步中找出的 (u) 一定不会存在其它的点再来更新 (d[u]) 此时的 (d[u]) 已经是从起点到 (u) 的最短路径。我们不断选择确定为最小值的点进行标记和拓展，最终就可以得到起点到每个节点的最短路径。
朴素算法
void dijkstra()
{
bool vis[N];
memset(d,0x3f,sizeof d);
memset(vis,0,sizeof vis);
d[st]=0;
while(1)
{
int u=-1;
for(Re int i=1;i<=n;i++)
{
if(!vis[i]&&(u==-1||d[i]<d[u]))
{
u=i;
}
}
if(u==-1) break;
vis[u]=1;
for(Re int i=0;i<g[u].size();i++)
{
int to=g[u][i].id;
int Len=g[u][i].d;
if(d[to]>d[u]+Len)
{
d[to]=d[u]+Len;
}
}
}
}
算法优化
然而，我们发现该程序的时间复杂度虽然只有 (O(n^2)) ，但仍然无法满足大多数题目的要求。
于是，我们便考虑用一些操作来优化上述步骤。
优先队列 ( priority_queue )
这就是所谓的堆优化 ( ext{Dijkstra}) ，是较为常用的优化方式。
我们考虑用堆对 (d) 数组进行维护，共进行的 (n) 次操作，每次用 (O(log n)) 的时间取出堆顶元素并删除；共用 (O(mlog n)) 遍历每条边。故总时间复杂度为 (O((n+m)log n))。
struct Node {
int id,d;
bool operator < (const Node &a) const{
return d>a.d;
}
};
void dijkstra()
{
bool vis[N];
memset(d,0x3f,sizeof d);
memset(vis,0,sizeof vis);
d[st]=0;
priority_queue<Node> q;
q.push((Node){st,0});
while(!q.empty())
{
int u=q.top().id;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(Re int i=0;i<g[u].size();i++)
{
int to=g[u][i].id;
int Len=g[u][i].d;
if(d[to]>d[u]+Len)
{
d[to]=d[u]+Len;
q.push((Node){to,d[to]});
}
}
}
}
但是上述代码需要事先写一个结构体，有没有办法可以避免呢？
于是我们考虑使用 ( ext{pair}) 数组。
pair 数组
由于 ( ext{pair}) 数组有自带的比较函数，因此，我们可以省去上述的结构体。
但是我们需要注意一点，就是在入队的时候需要加入的是 (-d[v]) 而不是 (d[v]) ！
void dijkstra()
{
bool vis[N];
memset(d,0x3f,sizeof d);
memset(vis,0,sizeof vis);
d[st]=0;
priority_queue<pair<int,int> > q;
q.push(make_pair(0,st));
while(!q.empty())
{
int u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(Re int i=0;i<g[u].size();i++)
{
int to=g[u][i].id;
int Len=g[u][i].d;
if(d[to]>d[u]+Len)
{
d[to]=d[u]+Len;
q.push(make_pair(-d[to],to));
}
}
}
}