前言

        最短路径是求在一张有向图中，起点到终点的距离。求最短路径的方法有很多，如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，再见！

本文链接：https://blog.faryou.eu.org/post/108.html 转载需经作者授权！