【信息科学与工程学】计算机科学与自动化——第一百四十四篇 离散数学算法01

编号 1字段内容编号1类型图论算法领域离散数学 / 计算机科学算法类型单源最短路径（非负权）问题给定带权有向图 G=(V,E)，边权非负，求从源点 s 到所有其他顶点的最短路径长度。问题的数学分析及算法分析及算法逐步推理思考的数学方程式数学分析：设 dist[v] 为从 s 到 v 的最短距离，初始 dist[s]=0，其余为 ∞。每次从未确定最短路的顶点中选择 dist 最小的顶点 u，松弛其出边 (u,v)：若 dist[u]+w(u,v) dist[v]，则更新 dist[v]。该过程基于贪心策略，证明见 Dijkstra 算法正确性。算法步骤：1. 初始化 dist 数组，优先队列 Q 存储 (dist, vertex)。2. 当 Q 非空：