企业官网建设流程全解析

目录

一、本题题目

二、本题代码

三、关键思路

四、注意事项

五、图论角度

六、Dijkstra算法的两种版本求最短路径的区别

七、为什么要用这个堆优化版

八、自我感觉

一、本题题目

// 展示完整题目

二、本题代码

// 展示完整代码

三、关键思路

1、用小顶堆优化，用邻接表存储

2、三步走

//找距离源点最近的且未访问过的节点

//标记已访问过的

//更新未访问过的节点到源点的最短路径

四、注意事项

1、关于各种加入操作（C++语法）

// 数组用push_back()

// 队列、栈、优先级队列用push()

// 集合和map映射用insert()

2、operator()这是一个整体的函数调用运算符

3、如果代码里要显式调用构造函数，结构体里面要写出来

4、顶点编号是从1开始的，初始化起点的时候要注意初始化的是1

// 不是0

5、获取优先级队列的队头的时候要注意，要用一个数值对来接收

6.如果有问题要写调试代码段

7.这个版本的代码有很多变量、结构体、数组之类的，各种含义要搞清楚

// 比如cur的含义是当前遍历到的距离源点最近的且未访问过的节点数值对

// cur.first的含义是当前遍历到的距离源点最近的且未访问过的节点编号

五、图论角度

1、点的角度（例如：Prim算法求最小生成树，Dijkstra算法求最短路径）

2、边的角度（例如：Kruskal算法求最小生成树，堆优化版的Dijkstra算法求最短路径）

六、Dijkstra算法的两种版本求最短路径的区别

1、Dijkstra朴素版

【循环 + 邻接矩阵】

2、Dijkstra堆优化版

【小顶堆 + 邻接表】

// C++里面实现小顶堆用的是优先级队列

// 优先级队列可以自定义小顶堆/大顶堆

七、为什么要用这个堆优化版

时间复杂度更低

八、自我感觉

1、比朴素版的复杂，但是效率更好。果然好东西都是不那么容易拿到的。

2、小顶堆的相关操作有待提升，每次要写小顶堆的东西的时候，都重新自己写一遍

3、两种版本的时间复杂度

朴素版的时间复杂度是O（）

堆优化版的时间复杂度是O（eloge） // e是边的数量，有log是因为用堆排序的时候会出现log