白告山风

不定期更新摄影，acm题解等等有趣的东西~

0%

最短路径算法专题（初稿）

发表于 更新于 分类于 ，
本文字数： 3.7k 阅读时长 ≈ 3 分钟

​ 基本思路：首先从起点到所有可达的边进行查找，看是否能更新dist数组（dist[i]代表从源点到第i点的当前最短距离），同时在所有dist[i]中选择一个还没找到最短距离的点但是当前dist[i]是最短的点作为下次的起点，同时代表该点的最短距离被找到。一直循环，直到到达终点。每轮都能找到一个点的最短距离。

模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
const int inf=0x7fffffff;
const int N=1e3+8;
int dist[N],map1[N][N],pre[N];//dist[i]代表从起点到i点的当前最短距离，map1是邻接矩阵，pre[i]代表第i点的前一个点。
int start,targe,n;//start是起点，targe是终点。n是点的个数
int main(){
	scanf("%d%d",&start,&targe);
	//初始化dist和map每个元素都是inf，pre[i]=i,visit[i][j]=1
	//建图 map[i][j]=min(map[i][j],dis);防止重边
	dist[start]=0,visit[start]=0;
	while(start!=targe){
		int min=inf;
		int next=0;
		for(int i=1;i<=n;i++){
			if(map[start][i]!=inf){
			 if(dist[i]>map[start][i]+dist[start]){
			 dist[i]=map[start][i]+dist[start];//从源点到i的距离存在更短距离时，更新dist数组
			 pre[i]=start;//保存前驱
			 }
			}
			if(visit[i]&&dist[i]<min){//在还没找到最短距离的点找出到源点距离最短的
				next=i;
				min=dist[i];
			}
		}
		if(min==inf)break;//如果当前没能找到可以更新的点则退出循环。
		start=next,visit[start]=0;
	}
}
void  opt(int *pre,int end){//输出最短路径队列
 if(pre[end]!=end)opt(pre,pre[end]);
 printf("%d ",end);
}

​ 由上面的模板可以看出，我们朴素的dijkstra算法的时间复杂度大致为O(N^2),我们会发现，我们主要在邻接矩阵从起点，寻找可达的下一个点浪费了时间，以及寻找dist数组中的最小值时浪费了时间，那我们有什么办法可以将这个O(N)的遍历过程优化为O(logN)呢？

首先我们先解决邻接矩阵空间利用率低下而且遍历效率低下的问题，由于这里只需要我们找到可到的点，我们不妨用单链表将第一个点可以到的所有点串在一起，这样就减少了从一个点出发漫无目的的搜索，这里的单链表可以用动态数组vector定义一个数组map1

1
2
3
4
5
6
7
8
const int N=1e5+6;
struct roadmode{
    int to,dis;
};
vector<roadmode> map1[N];
for(int i=0;i<map1[start].size();i++){
    //map1[start][i]即为所有从start出发可以到达的点
}

或者我们还可以用链式前向星（下源码实现便是用的链式前向星）

接着我们还需要解决dist数组每轮寻找最小值需要消耗O(N)的问题，这个问题也很好解决，我们不妨维护一个小顶堆，配合一个vis数组即可解决。下面看具体实现代码。

dijkstra的堆优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>//邻接表加堆优化的dijkstra算法 
using namespace std;
const int maxn1=100004;
const int maxn2=200004;
int head[maxn1],dist[maxn1],visit[maxn1];//head[i]代表从i可达的第一条边在edge数组里的下标
int cnt,s,n,m;
typedef struct Edge{
	int to,dis,next;//to代表下一个点，dis代表距离，next代表从同一个点出发的下一条路在egde数组里的下标
}ID_Edge;//链式前向星的邻接表的基础元素，其中next相当于单链表中的指针部分 

ID_Edge edge[maxn2];//存放边的信息
void Add_edge(int from,int to,int dis){//增加一条边
	edge[++cnt].to=to;
	edge[cnt].dis=dis;
    
	edge[cnt].next=head[from];//下面这两句类似于头插法
	head[from]=cnt;
}//链式前向星（类似维护多个单链表，且采用的是头插法） 
struct Node{
	int id,dis;
	bool operator < (const Node &a) const{//重载运算符 定义为对象的dis变量越小优先度越高
		return a.dis<dis;
	}
};//堆优化的基本元素---利用优先队列 实现查询O(1),维护O(logn)的复杂度 
void dijkstra(){
	priority_queue<Node>q;//优先队列默认为小顶堆
	q.push((Node){s,0});

	for(int i=1;i<=n;i++){
		dist[i]=-1;
	}
		dist[s]=0;
	while(!q.empty()){
		Node a=q.top();//每次查询堆优化的dist队列中的最小值
		q.pop();
		if(visit[a.id]){//如果这个最小值早找到了最短路径，则跳过
			continue;
		}
		visit[a.id]=1;
		for(int i=head[a.id];i!=0;i=edge[i].next){//i代表从当前起点到另一点的边在edge里的下标
			if(dist[edge[i].to]==-1||(dist[a.id]+edge[i].dis<dist[edge[i].to])){//如果dist[edge[i].to]还没被到达过，或者存在更短的dist[edge[i].to]，就更新。
				dist[edge[i].to]=dist[a.id]+edge[i].dis;
				q.push((Node){edge[i].to,dist[edge[i].to]});//入堆
			}
		}
	}
	
}
int main(){
	 scanf("%d%d%d",&n,&m,&s);
	 for(int i=1;i<=m;i++){
	 	int u,v,w;
	 	scanf("%d%d%d",&u,&v,&w);
	 	Add_edge(u,v,w);
	 }	
 	dijkstra();
 	for(int i=1;i<=n;i++){
 		printf("%d ",dist[i]);
	 }
	 return 0;
}


我们不难发现，堆优化后，时间复杂度大概为O(Nlog(N))（我不知道为什么呜呜）。