用C++写出狄克斯特拉算法

用C++写出狄克斯特拉算法

• 引言
• 开始介绍
• 如何实现
• • 开始执行第一步
• 代码实现
• • 前期准备
  • 开始步入正题
  • 把它打包成类：
  • In The End
• 写在最后

引言

孟宇洋：绿幕君，我最近遇到一个问题
绿幕君：咋了这是？
孟宇洋：我要做一个地图算法，要求出两点之间最短路程。
绿幕君：不求最短路径？
孟宇洋：毕竟是缺德地图嘛。。。
绿幕君：。。。

开始介绍

遇到求最短权重的问题（不带负数，这个算法另当别论，咱们以后有空再讲），我们一般用Dijkstra（狄克斯特拉算法），它的效率可以吊打dfs（深度优先搜索）,相信在大厂上班的童鞋都有一个烦恼，那就是。。。

服务器又宕机了！效率怎么这么低？
微笑中流露着痛苦

如何实现

是个人都知道，要想打出一个算法，必须要知道它的原理！我先来画一个图：

这么细心的博主估计也没谁了，点个赞吧!

好的，现在来让我们慢慢往后推！

首先。。。

孟宇洋：设为无穷大！
绿幕君：讲得好！下次别讲了！

如图所示，我们将除了起点以外的所有地点都标上了99999

孟宇洋：So?
绿幕君：开始遍历！

开始执行第一步

标上最大值以后，我们要开始去找预设点
现在，我们从起点开始往外找。

圆形代表预设点，在B和C这两个预设点里，B最小，所以从B开始

这时，肯定会有大聪明站出来说

大聪明：为什么B不属于预设点了？？？？？

B已经被走过一次了，做过迷宫问题的小伙伴一定知道一种方法叫做 过河拆桥。

C因为这个机制¹，不会被重复列进预设点里。

现在要走最小的D

还是因为狄克斯特拉算法的机制，E无法被走，现在还剩下C和E，两数权重一样，本着人道主义的份上，我们选字母排行榜（字母表）中靠前亿些的C。

这时只剩下了F和E,咱们都不用看，一个14一个5，那肯定选E啊！
最后。。。

得到答案14。（提示：狄克斯特拉算法是用来求最小权重的，求最短路请老老实实用A*（以后会讲））

代码实现

前期准备

首先，定义一个优先队列：

priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > b;//保存运行到哪一个地方了

然后，定义一个map:

map<int,int>a;//权值存储

开始步入正题

啥也别讲了，先来一个函数：

int returnDikstalAnswer(vector<int> qz[],vector<int> lx[],int less){/*qz[x][y] = x和y之间的权值lx[x][i] = x和lx[x][i]之间有一条路less 一共有less个点*/
}

看完了上面的流程图，大家应该不难猜到它是一个广搜代码，所以。。。

a[0] = 0;
less-=1;
b.push({0,0});
while(!b.empty()){auto k = b.top();b.pop();
}//bfs基本操作

由于优先对列会帮我们排好序，所以每次都正常读就行了。
接下来开始加入预设点：

int j=0;
for(auto&i:lx[k.second]){auto it = a.find(i);if(it == a.end()){a[i] = k.first+qz[k.second][j];pair<int,int>bc(a[i],i);b.push(bc); }j+=1;
}

最后，返回 a[less] 即可。

把它打包成类：

class Dijkstra{
public:map<int,int>a;//权值存储priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > b;//保存运行到哪一个地方了int returnDikstalAnswer(vector<int> qz[],vector<int> lx[],int less){a[0] = 0;less-=1;b.push({0,0});while(!b.empty()){auto k = b.top();b.pop();int j=0;for(auto&i:lx[k.second]){auto it = a.find(i);if(it == a.end()){a[i] = k.first+qz[k.second][j];pair<int,int>bc(a[i],i);b.push(bc); }j+=1;}}return a[less];}
};

In The End

我们来写一下主函数：

int main() {int n,q;cin>>n>>q;vector<int>qz[200],lx[200];//可改for(int i=0;i<q;i++){int x,y,z;cin>>x>>y>>z;lx[x].push_back(y);qz[x].push_back(z);}cout<<Dijkstra().returnDikstalAnswer(qz,lx,n);
}

运行效果：
cin:
7 9
0 2 5
0 1 2
1 2 6
1 3 1
3 4 4
1 4 3
4 6 9
2 5 8
5 6 7
cout:
14
timeout:0ms

写在最后

建议自己先动脑写一下！
算法参考《我的第一本算法书》4.6章狄克斯特拉算法
编辑器使用leetcode的playground。（代码分享地址狄克斯特拉算法实现伪代码-leetcode)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！