路径规划——Dijkstra算法

Answer 1

Dijkstra算法是一种用于解决赋权有向图或无向图中单源最短路径问题的贪心策略。算法最终产生的是一个最短路径树。算法的运行基于以下特点：使用一个数组dis来记录从源点到所有其他顶点的最短路径，以及一个集合T用于存储已找到最短路径的顶点。
算法初始化时，源点s的路径权重设为0，对于与s相连的直接边(s, m)，dis[m]设为边权w(s, m)，其他顶点路径设为无穷大。初始时，集合T仅包含顶点s。
算法的核心逻辑是选择dis数组中的最小值，该值对应着源点到当前顶点的最短路径，将该点加入到集合T中。接着检查新加入的顶点是否可以到达其他顶点，并判断通过该顶点到达其他顶点的路径长度是否比源点直接到达的路径更短，若是，则更新这些顶点在dis中的值。这一过程重复直到集合T包含所有顶点。
以求解顶点v1到所有其他顶点的最短路径为例，首先声明dis数组，初始值设为无穷大，T仅包含v1。接下来，从dis数组中选择当前离v1最近的顶点，比如v3，此时dis[2]（下标从0开始）的值变为从“估计值”变为了“确定值”，即v1到v3的最短路径长度就是dis[2]的值。将v3加入T。由于v1到其他顶点的路径长度肯定大于v1到v3，因此v3为中转点时路径无法进一步缩短。
接着考虑v3的出度，检查路径v1–>v3–>v4的长度是否比v1–>v4更短。由于dis[3]为无穷大，而v1–>v3–>v4的长度为60，因此更新dis[3]的值，得到新的dis数组。这就是Dijkstra算法的核心思想：通过边来松弛源点到其他顶点的路径。
算法持续从dis数组中寻找最小值顶点，直至所有顶点加入T，最终得到所有顶点到源点的最短路径。
Dijkstra算法的时间复杂度与边数m和顶点数n有关。最简单的实现方法使用链表或数组存储顶点集合Q，搜索Q中最小元素的时间为O(m)。对于稀疏图，采用邻接表实现，时间复杂度优化至O(m log n)。使用堆作为优先队列，可以进一步提升性能，二叉堆的时间复杂度为O(m log n)，斐波纳契堆的性能更优，达到O(m + n log n)。
通过实例和代码实现可以更直观地理解Dijkstra算法的原理和应用。