单源最短路径--Dijkstra

Dijkstra的用途：

Dijkstra是一个求单源最短路径的算法。
"单源最短路径"，顾名思义，从一个源头到其他结点的最短路径。而这个算法，可以求出单个点对其他所有点的最短路径长度。（有些情况是Dijkstra不能处理的，比如负边权，遇到这类情况可能就需要使用其他算法了）

Dijkstra的思想：

主要思想：
从源结点开始，遍历源结点的所有连接的边，并进行排序，再从边的值最小的一个边开始遍历，在每一次遍历的过程中，都尝试更新所储存的某个结点对于源结点的最短路径长度（假设我们要到点B，目前我们遍历到了点A，如果点A到点B的距离加上点A到源点的距离比目前我们之前存储的 源点到点B的距离短的话，就更新源点到点B的最短路径，并在之后遍历连着点B的点（也就是进行BFS））。
例子：

首先，从源结点开始进行BFS（也就是遍历到达的点所向外连着的点.比如A->B B->A A->C（A连B，B连A，A连C），那么BFS A结点就是B C）
在BFS的过程中，每到一个点，就比较一下从源头到这个点的路径长度和之前求的从源头到这个点的最短路径的长度大小，如果现在这个路径长度比较小，就存起来

Dijkstra的实现方法：

首先，存图（使用邻接表或链式前向星（如果不会存图建议先学存图，因为这里不会讲怎么存图和BFS））.
算法运行过程：

把数据（也就是dis数组）初始化为INF（为什么要这样做？这是因为我们要使用较小的值不停更新它，这样最终就是源点到这个点的最小值了。那怎么知道某个点所对应的与源点的距离呢？一般是把源点的序号当做数组的下标。下标是什么意思呢？比如使用这个代码:int i=A[10]，10就是数组A的一个下标。源点的序号是什么意思呢？一般使用源点读入的顺序当做源点的序号）
准备一个优先队列，用于之后进行的BFS.
在BFS的过程中不断更新最小值，并且，如果一个点被更新了，就再把被更新的点推入优先队列，准备之后在这个点上进行BFS.
优化

Dijkstra的优化:

优化方法：
堆优化（这就是使用优先队列（这里我的代码使用了STL中的priority_queue）的原因）。因为我们是从源点开始遍历，并不停用离源点尽量小的点来更新其他点的当前最短路径，所以如果遍历队列中的结点时，发现这个结点中所存储的 向队列推入这个点时，这个点离源点的距离 与当前这个点到源点的最短路径不同的话，这是因为这个点的最短路径已经被别人更新过了，也就是说这个点的数据已经无法使用了。并且，在更新这个点的最短路径（在我的实现中使用了dis数组（这个括号内的内容并不重要，只是为了防止一些人不明白怎么更新这个点的最短路径））时，肯定已经把这个点推到队列中了。因此可以得出：如果这个点中储存的最短路径（我们用Node结构体，存储点的序号和将这个点推入队列时源点到这个点的最短路径）和目前的最短路径不一样，那么必然这个点中存储的最短路径是较长的，并且这个点已经无用了，只会造成重复计算 所以，当我们判断到这个条件时，就可以直接跳过这个结点。

Dijkstra的使用注意事项：

如果图是无向图，需要双向加边（也就是调用两次addEdge方法，比如A-B这条边就可以addEdge(a,b);addEdge(b,a)（这里忽略了权值））

模板题目地址：https://www.luogu.org/problemnew/show/P4779

重载运算符版：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int s,cnt=0,dis[1000010],head[1000010];
//s:源结点 cnt:边总数,用于存边 dis:存储当前的源结点到某个结点的最短路径长度(下标是结点序号) head:邻接表, 
struct Edge{
    int v,w,nxt;
}e[500010];
struct Node{
    int u,d;
    bool operator <(const Node& rhs)const{
        return d>rhs.d;//重载运算符，这个需要背过 
    }
};
void addEdge(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    //关于邻接表: 
    //首先要明确，邻接表是一个链式结构，也就是说，首先添加的边在邻接表的最后面
    //最后添加的在前面，在遍历的时候也是从头往后遍历，也就是说最先添加的反而最后被遍历到. 
    //当遍历到最后一个的时候 由于最后一个的后面已经没有结点了,那么此时i的值就成为了0(具体看下面的for循环代码)
    //成为0了,也就代表着循环该结束了.这时候,循环条件不成立,循环就结束了. 
    head[u]=cnt;
}
void dijkstra(){
    dis[s]=0;
    priority_queue<Node>q;
    q.push((Node){s,0});
    while(!q.empty()){
        Node now=q.top();q.pop();
        int d=now.d,u=now.u;
        if(d!=dis[u])continue;//堆优化，等同于 if(d>dis[u])continue;，可以相对较好地减少时间复杂度
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v,w=e[i].w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push((Node){v,dis[v]});
            }
        }
    }
}
int main(){
    int n,m;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;i++)dis[i]=2147483647;//将源结点到其他结点的路径长度初始化为尽可能大的值，也就是INF 
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        addEdge(x,y,z);
    }
    dijkstra();
    for(int i=1;i<=n;i++)printf("%d ",dis[i]);
    return 0;
}

Pair版：

#include<bits/stdc++.h>
#include<iostream>
#define P pair<long long,int>
#define INF 2147483647
#define maxn 500005
using namespace std;
priority_queue<P,vector<P>,greater<P> >q;
int dis[maxn],vis[maxn],head[maxn];
int n,m,s;
int cnt;
struct Edge{
    int u,v,w,next;
}e[maxn*2];
void add(int u,int v ,int w){
    e[++cnt].u=u;
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
} 
void dijkstra(){
    while(!q.empty()){
        int x=q.top().second;
        q.pop();
        if(!vis[x]){
            vis[x]=1;
            for(int i=head[x];i;i=e[i].next){
                int v=e[i].v;
                dis[v]=min(dis[v],dis[x]+e[i].w);
                q.push(make_pair(dis[v],v));
            }
        }
        
    }
    
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        dis[i]=INF;
    }
    dis[s]=0;
    q.push(make_pair(0,s));
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c); 
    }
    dijkstra();
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<" ";
    }
    cout<<endl;
    return 0;
        
}