Dijkstra 最短路径算法1 是用于查找带权有向图中两点最短路径的算法，也可以用来从一个节点出发，找寻到图中所有其它节点的最短路径的问题。其核心其实和最小生成树中的Prime 算法类似，是一个贪心算法。
特别注意
Dijkstra 算法并不能适用于有负数权重边的图，对于用负数权重的边，可以使用 Bellman-Ford 算法
其主要的算法过程如下：
将所有的节点分成两个集合，“已确定节点” 和 “未确定节点” （算法开始时，”已确定节点” 集合只包含起始节点）。
算法开始后，每次从 “未确定节点” 的集合中找到离 “已确定节点” 最近的节点，将其加入到 “已确定节点” 集合，并且更新 “未确定节点” 中的节点到 “已确定节点” 集合的最短距离。（这里只需考虑与选择节点连通的节点，如果通过选择节点访问时，其距离比通过其它 “已确定节点” 访问的距离短，则找到了一条更短的路径，更新其距离）
重复这一过程，直到我们遇到目标节点，或者访问到了所有节点。
优化
算法过程中我们需要一直查找最短的距离，所以我们可以考虑使用小顶堆来优化我们查找的速度。
时间复杂度：
| 算法 | 最坏时间复杂度 |
|---|---|
| 使用邻接表的戴克斯特拉算法 | |
| 使用二叉堆优化的戴克斯特拉算法 |