聊聊Dijkstra
noir
10月 02, 2020
简介
通常的，Dijkstra用于寻路，解决的是有权图中最短路径的问题，我们将做个题从一个例子来解释这件事。
做题
做题家们的首要准则，就是看题，看准题，如图：
求A到F的最短路径。
简单的分析一下：
- 有向有权
- 每一跳的最短路径都是上一跳加权最优选择
需要的额外空间
临接矩阵
记录扫描集合s={}
记录从起始点到对应位置距离的集合dis,默认为dis={∞,∞,∞,∞,∞,∞}
下面我们就这样表示：
开始寻路
- 从入口A开始
我们可以分析出距离当前集合最近的是B - A -> B
此时，可知距离当前集合最近的节点是D - A -> B -> D
此时，可知距离当前集合最近的节点是C - A -> B -> D -> C
此时距离当前集合最近的是节点e - A -> B -> D -> C -> E
此时发现距离当前集合最近的是终点，结束寻路，获取最短距离。
分析一下
整体Dijkstra感觉像是广度优先的变种，为了寻找最优不断的把扫描集合附件的点加入进来，整体的时间复杂度O(n^2)，可以预见的是n非常大而结果目标很远时整体的效率堪忧。
Leetcode相关题目：
刷完咱们去玩A*，爷青回！！！( •̀ ω •́ )y