前言:
今日温习了前段时间学习的Dijkstra算法我在复习这个算法的时候，常常因为没有初始化或者条件判断而错误。
现在让我来浅谈一下我对该算法的理解
概述：
该算法常常应用在处理单源最短路问题，具体的数学证明以及原理可以查百度。
大致是通过不断迭代找到当前最短路径，再通过该最短路径往后延伸，找到到终点的最短路径。
常见的Dijkstra算法分为朴素版以及堆优化版，前者的时间复杂度为O(N*N),后者的时间复杂度为O(MlogN)，其中N为点的个数，M为边的个数
朴素版用来处理稠密图，稠密图用邻接矩阵存储图，堆优化版用来处理稀疏图，稀疏图用邻接表存储图。
实践
长江游艇俱乐部在长江上设置了 n 个游艇出租站 1,2,……,n。游客可在这些游艇出租站租用游艇，并
在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为 r(i,j)（1<=i<=j）。
试设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。
解法一：朴素版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
|
using namespace std;
const int N=10010;
int g[N][N],dist[N];//g[N][N]表示相邻两点的距离，dist[N]表示从起点到某一点的最短路径
bool st[N];//st[N]表示该点是否被利用找过最短路径
int n;
int dijkstra(){
memset(dist,0x3f,sizeof dist);//初始化数组
dist[1]=0;//特殊情况特殊考虑
for(int i=0;i<=n-1;i++){//进行n-1次迭代找到最小路径
int t=-1;//为每一次迭代的初始点提供便利
for(int j=1;j<=n;j++){
if(!st[j]&&(t==-1||dist[t]>dist[j])){
t=j;//该点既要没被利用过同时也是目前的最短路径
}
}
for(int j=1;j<=n;j++){
dist[j]=min(dist[j],dist[t]+g[t][j]);//利用更新的点找最短路径
}
st[t]=true;//标记该点已被利用过
}
return dist[n];
}
int main(){
cin>>n;
memset(g,0x3f,sizeof g);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
cin>>g[i][j];
}
}
cout<< dijkstra();
return 0;
}
|
解法二: 堆优化版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
|
using namespace std;
typedef pair<int,int> PII;
const int N=1005;
bool st[N];
int a[N][N];
int w[N],h[N],ne[N],e[N],idx;//构建邻接表
int n,dist[N];
void add(int x,int y,int c){//连接边
w[idx]=c;
e[idx]=y;
ne[idx]=h[x];
h[x]=idx++;
}
int dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
priority_queue<PII,vector<PII>,greater<PII>>heap;//建立小顶堆，优先对第一个元素从小到大排序，其次才是第二个元素
heap.emplace(0,1);
while(heap.size()){
auto t=heap.top();//不断利用该当前最小路径点，找到最终最小路径
heap.pop();//利用过后排出
int ver=t.second,val=t.first;
if(st[ver])continue;
st[ver]=true;//将利用过的点打上标记
for(int i=h[ver];i!=-1;i=ne[i]){//利用该点更新最短路径
int j=e[i];
if(dist[j]>val+w[i]){
dist[j]=val+w[i];
heap.emplace(dist[j],j);
}
}
}
return dist[n];
}
int main(){
memset(a,0x3f,sizeof a);
memset(h,-1,sizeof h);
cin>>n;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
cin>>a[i][j];
add(i,j,a[i][j]);
}
}
cout<<dijkstra();
return 0;
}
|
