3
0016：单源最短路径（dijkstra算法） - uf0_金币灰黄^w.h
source link: https://www.cnblogs.com/wdrdsahudhisjabshdahuhsh/p/16457228.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
0016：单源最短路径（dijkstra算法）
题目链接：https://www.luogu.com.cn/problem/P4779
题目描述：给定一个 n 个点，m 条有向边的带非负权图，计算从 s 出发，到每个点的距离。
这道题就是一个单源最短路径的模板，有两种做法：
1.Floyd算法
暴力枚举出所有起点、终点以及中间值，然后算出每两个点间的最小值。
但这个算法时间复杂度较高，是O（n^3），很容易爆掉，在这道题甚至拿不到分。
1 #include<bits/stdc++.h>
2 using namespace std;
3 int arr[10000][10000];
4 int main(){
5 int n,m,s,i,j,k,a,b,c;
6 cin>>n>>m>>s;
7 for(i=1;i<=n;i++){
8 for(j=1;j<=n;j++){
9 if(i==j){
10 arr[i][j]=0;
11 }else{
12 arr[i][j]=99999999;
13 }
14 }
15 }
16 while(m--){
17 cin>>a>>b>>c;
18 arr[a][b]=min(c,arr[a][b]);
19 }
20 for(k=1;k<=n;k++){
21 for(i=1;i<=n;i++){
22 if(i==k||arr[i][k]==99999999){
23 continue;
24 }
25 for(j=1;j<=n;j++){
26 arr[i][j]=min(arr[i][j],arr[i][k]+arr[k][j]);
27 }
28 }
29 }
30 for(i=1;i<=n;i++){
31 cout<<arr[s][i]<<" ";
32 }
33 }
这道题我们要用一种更高级的算法——
2.dijkstra算法
在无负权边的情况下，时间复杂度为 O（n log n）基本可以顺利通过所有模板题。
先确定初始点到其他所有点的路径（可能为无穷），然后从和该点距离最小点开始遍历，不断更新这些点与初始点的最小距离（学术名叫松弛），最后求出初始点与所有其他点的最短路。
然后要通过此题，还需要前向星存边和优先队列（堆）优化，可能比较难理解，自己画图模拟即可。
上代码（有注释）：
1 #include<bits/stdc++.h>
2 using namespace std;
3 long long vis[100001]={0},head[100001],dis[100001],cnt,n,m,s,a,b,c;
4 long long INF=2147483647;//2的31次方，可以看做无穷
5 struct Q{
6 int a,b,c,next;
7 };//邻接表，在有向图中存储起点、终点权值，next用来前向星存边
8 struct node{//放进优先队列中的结构体
9 int w,now;//w为最短路，now为点
10 bool operator <(const node &x)const{
11 return w>x.w;//权值从大到小排
12 }
13 };
14 priority_queue<node> q;//优先队列
15 Q e[500001];
16 void add(int a,int b,int c){//前向星存边
17 e[cnt++].a=a;
18 e[cnt].b=b;
19 e[cnt].c=c;
20 e[cnt].next=head[a];//next存储上一个cnt值，方便for循环从后往前遍历边
21 head[a]=cnt;
22 }
23 void dijkstra(){
24 for(int i=1;i<=n;i++){
25 dis[i]=INF;
26 }
27 dis[s]=0;
28 q.push((node){0,s});//将起点压入队列
29 while(!q.empty()){//队列非空
30 node x=q.top();//弹出堆顶（最小）元素
31 q.pop();
32 int u=x.now;
33 if(vis[u]==1){
34 continue;//遍历完无需再遍历
35 }
36 vis[u]=1;
37 for(int i=head[u];i;i=e[i].next){//用前向星遍历
38 int v=e[i].b;
39 dis[v]=min(dis[v],dis[u]+e[i].c);//松弛操作
40 q.push((node){dis[v],v});
41 }
42 }
43 }
44 int main(){
45 cin>>n>>m>>s;
46 for(int i=0;i<m;i++){
47 cin>>a>>b>>c;
48 add(a,b,c);
49 }
50 dijkstra();
51 for(int i=1;i<=n;i++){
52 cout<<dis[i]<<" ";
53 }
54 }
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK