前言:

[HTML_REMOVED]今日温习了前段时间学习的Dijkstra算法我在复习这个算法的时候，常常因为没有初始化或者条件判断而错误。

现在让我来浅谈一下我对该算法的理解[HTML_REMOVED]

概述：

[HTML_REMOVED]该算法常常应用在处理单源最短路问题，具体的数学证明以及原理可以查百度。

大致是通过不断迭代找到当前最短路径，再通过该最短路径往后延伸，找到到终点的最短路径。

常见的Dijkstra算法分为朴素版以及堆优化版，前者的时间复杂度为O(N*N),后者的时间复杂度为O(MlogN)，其中N为点的个数，M为边的个数

朴素版用来处理稠密图，稠密图用邻接矩阵存储图，堆优化版用来处理稀疏图，稀疏图用邻接表存储图。[HTML_REMOVED]

实践

题目:租用游艇

[HTML_REMOVED]长江游艇俱乐部在长江上设置了 n 个游艇出租站 1,2,......,n。游客可在这些游艇出租站租用游艇，并

在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为 r(i,j)（1<=i<=j）。

试设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。[HTML_REMOVED]

解法一：朴素版Dijkstra

#include<bits/stdc++.h>
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

#include<bits/stdc++.h>
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;
}

版权声明:

本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自大黄的博客！
欢迎来我的博客浏览其他文章

前言:

概述：

实践

题目:租用游艇

解法一：朴素版Dijkstra

解法二: 堆优化版Dijkstra

版权声明:

0 评论