最短路径算法：Dijkstra算法 描述 Dijkstra算法用于在 带权有向图 中求解单源最短路径问题，即从某个源点出发，到图中所有其他顶点的最短路径。该算法要求边的权重 非负 ，其核心思想是采用 贪心策略 ，逐步确定离源点最近的顶点，并利用这些顶点更新相邻顶点的最短距离。 解题过程 步骤1：初始化距离数组 创建一个数组 dist[] ，用于记录源点到每个顶点的当前最短距离。初始时，源点的距离设为0（即 dist[source] = 0 ），其他顶点的距离设为无穷大（表示尚未可达）。 创建一个优先队列（最小堆）或集合，用于动态选择当前距离最小的顶点。初始时将源点加入队列。 步骤2：选择当前距离最小的顶点 从队列中取出当前 dist 值最小的顶点 u （首次取出的必然是源点）。此时 u 的最短距离已确定（贪心选择：因为所有边权非负，不可能通过其他路径得到更短距离）。 若队列为空，则算法结束。 步骤3：松弛操作（更新相邻顶点距离） 遍历顶点 u 的所有邻接顶点 v ，检查是否存在更短路径： 若 dist[u] + weight(u, v) < dist[v] ，则更新 dist[v] = dist[u] + weight(u, v) ，并将 v 加入队列（若使用堆，需调整堆结构）。 此步骤确保通过 u 中转可能缩短到 v 的距离。 步骤4：重复步骤2-3 重复上述过程，直到所有顶点均被处理（即队列为空）。最终 dist[] 数组存储的即为源点到各顶点的最短距离。 关键细节 非负权要求 ：若存在负权边，贪心选择可能失效，因为通过负权边可能使已确定最短距离的顶点产生更短路径。 时间复杂度 ： 使用数组遍历选择最小顶点：O(V²)（适合稠密图）。 使用最小堆：O((V+E)logV)（适合稀疏图）。 路径记录 ：可通过 prev[] 数组记录路径上前驱节点，反向回溯得到完整路径。 举例说明 以图为例：顶点集{A,B,C,D}，边权为A→B(4), A→C(2), B→C(1), B→D(5), C→D(8)。源点为A： 初始 dist[A]=0 , 其他为∞。 取A，更新B=4, C=2。 取C（当前最小），通过C更新D=2+8=10。 取B，通过B更新C=min(2, 4+1)=2（不变），更新D=min(10,4+5)=9。 最终 dist[D]=9 ，路径A→B→D。 通过逐步贪心选择，算法确保每次扩展的顶点距离最短，最终得到全局最优解。