图论中的最短路径问题（Dijkstra算法）

题目描述
给定一个带权有向图（或无向图），其中每条边的权重为非负值，并指定一个起点（源点）。要求找出从源点到图中所有其他顶点的最短路径长度（即路径上各边权重之和的最小值）。例如，在路由网络或地图导航中，我们需要找到从一个城市到其他所有城市的最短距离。

解题过程
Dijkstra算法的核心是贪心策略：每次选择当前距离源点最近的未处理顶点，通过该顶点更新其邻居的距离。以下是详细步骤：

1. 初始化

   • 创建一个距离数组dist[]，其中dist[v]表示源点到顶点v的当前最短距离估计。初始时，dist[源点] = 0，其他顶点设为无穷大（表示尚未可达）。
   • 创建一个集合（或优先队列）用于存储未处理的顶点，初始包含所有顶点。
   • 可选：使用一个前驱数组prev[]记录路径（本例重点为距离计算）。

2. 主循环
   重复以下步骤直到所有顶点被处理：
   a. 选择当前最小距离顶点：从未处理顶点中选出dist值最小的顶点u（首次迭代时必为源点）。
   b. 标记为已处理：将u移出未处理集合，此时dist[u]已是最终最短距离（因非负权重保证）。
   c. 松弛操作：遍历u的所有邻居顶点v，若通过u到v的路径更短，则更新dist[v]：

   如果 dist[u] + weight(u, v) < dist[v]：
       更新 dist[v] = dist[u] + weight(u, v)
       更新前驱信息（若需要）
   

3. 终止条件
   当所有顶点被处理时，dist[]中存储的即为源点到各顶点的最短距离。

关键点说明

• 非负权重必要性：若存在负权边，可能破坏贪心选择正确性（已处理的顶点距离可能被后续路径刷新）。
• 数据结构优化：使用最小堆（优先队列）可高效选择最小距离顶点，将时间复杂度从O(V²)优化至O((V+E) log V)。
• 无向图与有向图的处理方式相同，只需将每条无向边视为双向有向边。

示例演示
假设图有顶点{A, B, C, D}，源点为A，边权重为：A→B(4), A→C(2), B→C(1), B→D(5), C→D(8)。

• 初始化：dist[A]=0, 其他为∞。
• 处理A：更新B(4), C(2)。
• 选择最小顶点C：通过C更新D(2+8=10)。
• 处理B：通过B更新C(4+1=5，但C已确定更小值2，故忽略)，更新D(4+5=9，优于10)。
• 最终dist: A(0), B(4), C(2), D(9)。

通过以上步骤，可系统性地找到所有最短路径。