图论中的最短路径问题（Dijkstra算法） 题目描述 在一个 非负权有向图 中，给定一个起点 \( s \)，要求找出从 \( s \) 到图中所有其他顶点的最短路径长度。其中，路径长度定义为路径上所有边的权值之和。例如，下图包含顶点 A、B、C、D，边权均为非负数，求从 A 到其他顶点的最短距离。 解题过程 核心思想 Dijkstra 算法采用 贪心策略 ，逐步确定从起点到各顶点的最短距离。其核心是维护一个集合 \( S \)，包含已确定最短距离的顶点，并不断从剩余顶点中选取当前距离起点最近的顶点加入 \( S \)，同时更新该顶点的邻居的距离。 算法步骤 初始化 ： 设置起点 \( s \) 的距离 \( dist[ s ] = 0 \)，其他顶点的距离初始化为无穷大（表示尚未到达）。集合 \( S \) 初始为空。 使用优先队列（最小堆）存储顶点及其当前距离，初始时将起点入队。 迭代过程 ： 从优先队列中取出当前距离最小的顶点 \( u \)（即未加入 \( S \) 的最近顶点）。 将 \( u \) 加入集合 \( S \)，表示 \( dist[ u ] \) 已确定为最终最短距离。 遍历 \( u \) 的所有邻居 \( v \)： 若 \( v \) 未在 \( S \) 中，且通过 \( u \) 到 \( v \) 的距离更短（即 \( dist[ u] + w(u, v) < dist[ v] \)），则更新 \( dist[ v] = dist[ u ] + w(u, v) \)，并将 \( v \) 及其新距离加入优先队列（或更新队列中 \( v \) 的距离）。 重复以上步骤，直到所有顶点均加入 \( S \)（或优先队列为空）。 举例说明 以如下有向图为例（边权非负）： 求从 A 到所有顶点的最短路径： 初始化 ：\( dist[ A]=0 \), \( dist[ B]=dist[ C]=dist[ D]=\infty \)，优先队列：[ (A,0) ]。 第1轮 ：取出 A，更新邻居 B 和 C： \( dist[ B] = 0+1=1 \), \( dist[ C ] = 0+4=4 \)。 队列变为：[ (B,1), (C,4) ]。 第2轮 ：取出 B，更新邻居 C 和 D： \( dist[ C] = min(4, 1+2)=3 \), \( dist[ D ] = 1+6=7 \)。 队列变为：[ (C,3), (D,7) ]。 第3轮 ：取出 C，更新邻居 D： \( dist[ D ] = min(7, 3+3)=6 \)。 队列变为：[ (D,6) ]。 第4轮 ：取出 D，无邻居可更新。 最终结果：\( dist[ A]=0 \), \( dist[ B]=1 \), \( dist[ C]=3 \), \( dist[ D ]=6 \)。 关键细节 非负权要求 ：若边权为负，贪心选择可能错误（因为后续可能通过负权边缩短距离）。 时间复杂度 ：使用优先队列时为 \( O((V+E) \log V) \)，其中 \( V \) 为顶点数，\( E \) 为边数。 为什么贪心有效 ：每次选取当前距离最小的顶点，由于其边权非负，后续路径不可能比当前路径更短。 应用场景 适用于网络路由、地图导航等需要非负权最短路径的场景。若存在负权边，需使用 Bellman-Ford 算法。