图论：最短路-Dijkstra

Dijkstra+堆优化具有稳定的时间复杂度，在一些数据范围要求比较严格（准确来说是图比较苛刻）的时候能够保证稳定的时间复杂度

但是Dijkstra不能够解决负边权的问题，所以在使用的时候一定要仔细读题

如果题目说了边权非负，首选Dijkstra算法，如果图不是一些特殊的数据，可以尝试SPFA算法，毕竟在稀疏图面前，SPFA有着绝对的优势

Dijkstra和Prim很相似，它们的区别主要是d的含义，前者是到s的临时最短距离，后者是到树的临时最短距离，相同点是，每次找d最小的更新其它点的距离

然后，我们开始介绍用法：

int s,n,m,cnt;
int g[maxn],d[maxn];
struct Edge{int u,t,w,next;}e[maxm];
struct HeapNode{int d,u;bool operator <(const HeapNode& x) const{return d>x.d;}};
priority_queue<HeapNode> q;

在Bellman-Ford中相同的字眼我们不介绍，意义一致

HeapNode结构体和优先队列用来实现一个最小堆，堆元素是点，记录了节点号和距离值

void dijkstra(int s)
{
    for(int i=1;i<=n;i++) d[i]=INF;
    d[s]=0;
    HeapNode p;
    p.d=0;p.u=s;q.push(p);
    while(!q.empty())
    {
        HeapNode x=q.top(); q.pop();
        int u=x.u;
        if(x.d!=d[u]) continue;
        for(int tmp=g[u];tmp;tmp=e[tmp].next)
        if(d[e[tmp].t]>d[u]+e[tmp].w)
        {
            d[e[tmp].t]=d[u]+e[tmp].w;
            p.d=d[e[tmp].t];p.u=e[tmp].t;q.push(p);
        }
    }
}

如果你能够写明白邻接矩阵的Dijkstra算法，这里具有完全一致的意义，只不过用最小堆来找距离当前点集距离最小的点，把一遍遍历变成了Log级别的

然后这里的Dijkstra算法如果用邻接矩阵的话，就是被打回原形了，所以一定要用邻接表或者邻接数组来存储

下面给出完整实现：

 1 #include<cstdio>
 2 #include<queue>
 3 #include<cstring>
 4 using namespace std; 
 5 const int INF=0x7fffffff;
 6 const int maxn=100005;
 7 const int maxm=200005;
 8 int s,n,m,cnt;
 9 int g[maxn],d[maxn];
10 struct Edge{int u,t,w,next;}e[maxm];
11 struct HeapNode{int d,u;bool operator <(const HeapNode& x) const{return d>x.d;}};
12 priority_queue<HeapNode> q;
13 void addedge(int x,int y,int z)
14 {
15     cnt++;e[cnt].u=x;e[cnt].t=y;e[cnt].w=z;
16     e[cnt].next=g[x];g[x]=cnt;
17 }
18 void dijkstra(int s)
19 {
20     for(int i=1;i<=n;i++) d[i]=INF;
21     d[s]=0;
22     HeapNode p;
23     p.d=0;p.u=s;q.push(p);
24     while(!q.empty())
25     {
26         HeapNode x=q.top(); q.pop();
27         int u=x.u;
28         if(x.d!=d[u]) continue;
29         for(int tmp=g[u];tmp;tmp=e[tmp].next)
30         if(d[e[tmp].t]>d[u]+e[tmp].w)
31         {
32             d[e[tmp].t]=d[u]+e[tmp].w;
33             p.d=d[e[tmp].t];p.u=e[tmp].t;q.push(p);
34         }
35     }
36 }
37 int main()
38 {
39     scanf("%d%d%d",&n,&m,&s);
40     int x,y,z;
41     for(int i=1;i<=m;i++) {scanf("%d%d%d",&x,&y,&z);addedge(x,y,z);}
42     dijkstra(s);
43     for(int i=1;i<=n;i++) {printf("%d ",d[i]);}
44     return 0;
45 }