前言
最短路径是求在一张有向图中，起点到终点的距离。求最短路径的方法有很多，如SPFA、floyd、dijkstra等，今天我们学习dijkstra的思路与代码，其优点是时间复杂度和空间复杂度都很低，缺点是不能处理重边。

程序设计思路
dijkstra基于贪心实现，又有点类似DP，其思路大致如下：先把起点到所有点的距离都设为inf（一个很大的数），然后在所有与起点相连接的边中找到最短的一条，将这个新的点作为起点，并更新从起点出发到这个点的最短距离，直到找到终点。这个逐步更新的操作被称为松弛。

代码实现

洛谷上还有一道数据随机的模板题，这题专卡SPFA，但对我们的dijskla没有影响，下面是代码：

#include <bits/stdc++.h>
#define inf 2147483647
using namespace std;

struct Edge{//结构体用来存一条边的起点、终点、长度
    int to,dis,ne;
}edge[2000005];

int n,m,s,cnt,dist[2000005],head[2000005],x,y,z;//n、m、s如题意，cnt用来计数，dist存起点到各个点的最短距离
bool visit[2000005];//类似BFS中记录已经访问的点

void Add_edge(int from,int to,int w){//加入数组
    edge[++cnt].to=to;
    edge[cnt].dis=w;
    edge[cnt].ne=head[from];
    head[from]=cnt;
}

struct node{
    int id,dis;
    bool operator <(const node &a)const{ return a.dis<dis; }//优先队列升序排序
};
void dijkstra(){
    priority_queue<node> q;
    q.push(node{s,0});
    for(int i=1;i<=n;i++) dist[i]=inf;
    dist[s]=0;
    while(!q.empty()){
        node a=q.top();
        q.pop();//类似BFS的队列
        int now=a.id;
        if(visit[now]) continue;
        visit[now]=1;
        for(int i=head[now];i;i=edge[i].ne){//查所有边
            int j=edge[i].to;
            if(dist[now]+edge[i].dis<dist[j]){//判断走的这条路是不是比原来的更短
                dist[j]=dist[now]+edge[i].dis;
                q.push(node{j,dist[j]});
            }
        }
    }
}

int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        Add_edge(x,y,z);
    }
    dijkstra();
    for(int i=1;i<=n;i++) printf("%d ",dist[i]);
    return 0;
}

结语
dijkstra不能处理重边，这一点在选择方法时需要注意。我是faryou，再见！