什么是 Dijkstra算法

Dijkstra算法是一种用于在加权有向图或无向图中找到最短路径的算法。该算法由荷兰计算机科学家 Edsger W. Dijkstra 在1956年提出。它以起始节点为基准，逐步计算到其他节点的最短路径。

Dijkstra算法的基本思想是通过贪心策略，不断选择当前距离起点最近的节点，并更新与其相邻节点的距离。具体步骤如下：

1. 创建一个距离表，记录起始节点到各个节点的当前最短距离，初始时起始节点的最短距离为0，其他节点的最短距离设为无穷大。
2. 创建一个集合用于存储已经确定最短路径的节点。
3. 从起始节点开始，计算起始节点到所有相邻节点的距离，并更新距离表。
4. 从未确定最短路径的节点中选择距离最小的节点，并将其加入到已确定最短路径的节点集合中。
5. 更新新加入节点的相邻节点的距离，如果通过新加入节点到达相邻节点的距离比当前记录的最短距离小，则更新最短距离。
6. 重复步骤4和步骤5，直到所有节点都加入了已确定最短路径的节点集合或者没有可以更新的距离。

最终，Dijkstra算法会得到起始节点到所有其他节点的最短路径和最短距离。该算法适用于没有负权边的图，并且对于稠密图或边数较多的图，其时间复杂度为O(V^2)，其中V为节点数。优化后的算法，如使用最小堆数据结构来选择下一个节点，可以将时间复杂度降低到O((E+V)logV)，其中E为边数。