关于图论【最短路径之Dijkstra算法（堆优化版）|卡码网47.参加科学大会的思考】

目录一、本题题目二、本题代码三、关键思路四、注意事项五、图论角度六、Dijkstra算法的两种版本求最短路径的区别七、为什么要用这个堆优化版八、自我感觉一、本题题目// 展示完整题目二、本题代码// 展示完整代码三、关键思路1、用小顶堆优化用邻接表存储2、三步走//找距离源点最近的且未访问过的节点//标记已访问过的//更新未访问过的节点到源点的最短路径四、注意事项1、关于各种加入操作C语法// 数组用push_back()// 队列、栈、优先级队列用push()// 集合和map映射用insert()2、operator()这是一个整体的函数调用运算符3、如果代码里要显式调用构造函数结构体里面要写出来4、顶点编号是从1开始的初始化起点的时候要注意初始化的是1// 不是05、获取优先级队列的队头的时候要注意要用一个数值对来接收6.如果有问题要写调试代码段7.这个版本的代码有很多变量、结构体、数组之类的各种含义要搞清楚// 比如cur的含义是当前遍历到的距离源点最近的且未访问过的节点数值对// cur.first的含义是当前遍历到的距离源点最近的且未访问过的节点编号五、图论角度1、点的角度例如Prim算法求最小生成树Dijkstra算法求最短路径2、边的角度例如Kruskal算法求最小生成树堆优化版的Dijkstra算法求最短路径六、Dijkstra算法的两种版本求最短路径的区别1、Dijkstra朴素版【循环 邻接矩阵】2、Dijkstra堆优化版【小顶堆 邻接表】// C里面实现小顶堆用的是优先级队列// 优先级队列可以自定义小顶堆/大顶堆七、为什么要用这个堆优化版时间复杂度更低八、自我感觉1、比朴素版的复杂但是效率更好。果然好东西都是不那么容易拿到的。2、小顶堆的相关操作有待提升每次要写小顶堆的东西的时候都重新自己写一遍3、两种版本的时间复杂度朴素版的时间复杂度是O堆优化版的时间复杂度是Oeloge // e是边的数量有log是因为用堆排序的时候会出现log