北京大学郭炜教授讲解Dijkstra算法及应用

"最短路算法.pdf"是一份关于单源最短路径问题的讲义，主要讲解了Dijkstra算法，这是一种在带权有向图或无向图中寻找从源点到其他所有节点最短路径的经典算法。Dijkstra算法采用贪心策略，它通过逐步构建距离源点最近的点集合P，并更新每个未访问节点的距离估计值d[i]。 算法的核心步骤如下： 1. 初始化：设源点s的d[s]为0，其余节点的d[i]为正无穷大，P为空集合。 2. 寻找未加入P且距离最小的节点i，将其加入集合P。 3. 对于所有不在P中的节点j，如果d[i]+cost(i,j)小于当前的d[j]，则更新d[j]的值。 4. 使用邻接表数据结构存储图，原始版本的时间复杂度为O(V^2 + E)，其中V是节点数，E是边数。通过引入优先队列（如堆）优化，可以将时间复杂度降低至O(ElgV)。使用更高效的斐波那契堆数据结构，可以进一步优化为O(VlogV + E)。 5. 若需要输出最短路径，可利用一个prev数组记录每个节点的前驱节点，以便在更新距离时同时更新路径信息。 讲义还提及了Dijkstra算法的应用场景，比如在POJ3159Candies问题中，这是一个关于分配糖果的问题，涉及到3000个孩子和150000个关系，目标是找到第N个孩子最多能比第1个孩子多分多少糖果，这个问题可以通过构建一个稀疏图并应用Dijkstra算法来解决单源最短路径问题。 然而，Dijkstra算法有一个限制，即不适用于存在负权边的图，因为其算法原理依赖于边的非负权重。如果图中有负权重边，可能需要采用其他算法，如Bellman-Ford算法或者Floyd-Warshall算法来处理。总体而言，这份讲义提供了学习和理解Dijkstra算法的基础，并展示了其实用性和局限性。