用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,vector>,greater> > b;//保存运行到哪一个地方了

然后，定义一个map:

mapa;//权值存储

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

int returnDikstalAnswer(vector qz[],vector lx[],int 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];
        pairbc(a[i],i);
        b.push(bc); 
	 }
     j+=1;
}

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

class Dijkstra{
public:
    mapa;//权值存储
    priority_queue,vector>,greater> > b;//保存运行到哪一个地方了
    int returnDikstalAnswer(vector qz[],vector 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];
                    pairbc(a[i],i);
                    b.push(bc); 
                }
                j+=1;
            }
        }
        return a[less];
    }
};

我们来写一下主函数：

int main() {
    int n,q;
    cin>>n>>q;
    vectorqz[200],lx[200];//可改
    for(int i=0;i
        int x,y,z;
        cin>>x>>y>>z;
        lx[x].push_back(y);
        qz[x].push_back(z);
    }
    cout< 
运行效果：
 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)
 
 
 
 
和B一样，B因为这个机制，就不会再被走一次，但因为这个机制，狄克斯特拉算法不能走带负权的边。 ↩︎