0016：单源最短路径（dijkstra算法）

题目链接：https://www.luogu.com.cn/problem/P4779

题目描述：给定一个 n 个点，m 条有向边的带非负权图，计算从 s 出发，到每个点的距离。

 

 

 

 

这道题就是一个单源最短路径的模板，有两种做法：

1.Floyd算法

暴力枚举出所有起点、终点以及中间值，然后算出每两个点间的最小值。

但这个算法时间复杂度较高，是O（n^3），很容易爆掉，在这道题甚至拿不到分。

代码：

#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）基本可以顺利通过所有模板题。

先确定初始点到其他所有点的路径（可能为无穷），然后从和该点距离最小点开始遍历，不断更新这些点与初始点的最小距离（学术名叫松弛），最后求出初始点与所有其他点的最短路。

然后要通过此题，还需要前向星存边和优先队列（堆）优化，可能比较难理解，自己画图模拟即可。

上代码（有注释）：

#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 }