Dijkstra算法

题目描述
在一个带权有向图中，给定一个源点（起始节点），要求找出从源点到图中所有其他节点的最短路径长度。图的边权值均为非负数。

解题过程

1. 问题分析

   • 我们需要找到从单个源点到所有其他节点的最短路径
   • 边权值非负的特性使得我们可以使用Dijkstra算法
   • 算法核心思想：每次选择当前距离源点最近的未访问节点，通过该节点更新其邻居节点的距离

2. 数据结构准备

   • 距离数组dist：记录源点到每个节点的当前最短距离，初始时源点距离为0，其他为无穷大
   • 访问标记数组visited：记录每个节点是否已被处理
   • 优先队列（最小堆）：按距离从小到大存储节点，便于快速获取当前距离最小的节点

3. 算法步骤

   • 初始化：将源点加入优先队列，距离设为0
   • 循环执行以下步骤直到队列为空：
     a. 从优先队列中取出当前距离最小的节点u
     b. 标记节点u为已访问
     c. 遍历u的所有未访问邻居节点v：
     • 计算经过u到v的距离：newDist = dist[u] + weight(u,v)
     • 如果newDist小于当前记录的dist[v]，则更新dist[v] = newDist
     • 将v加入优先队列（如果不在队列中）或调整v在队列中的位置

4. 关键点解释

   • 贪心策略：每次选择当前最短路径的节点，这个选择是全局最优的
   • 非负权值保证：确保一旦节点被标记为已访问，其最短距离就不再改变
   • 时间复杂度：使用优先队列时为O(ElogV)，其中E为边数，V为节点数

5. 示例说明
   考虑一个简单图：节点0->1（权重4），0->2（权重1），2->1（权重2）

   • 初始：dist[0]=0，其他为∞
   • 处理节点0：更新邻居1(4)、2(1)
   • 处理节点2：通过2到1的距离为1+2=3＜4，更新dist[1]=3
   • 最终结果：0->0:0，0->1:3，0->2:1

算法特点

• 仅适用于非负权图
• 能够找到单源到所有节点的最短路径
• 是广度优先搜索在带权图中的推广