单源最短路

一、问题简介

给定一张带权有向/无向图 ，指定一个起点 ，求起点 到图中所有其余节点的最短路径长度，该问题称为单源最短路。

设节点总数为 ，边总数为 。 记 表示起点 到节点 的最短距离，初始状态：

二、松弛操作（核心基础）

对一条边 ，边权为 。 若满足：

则更新：

该过程称为松弛，是所有最短路算法的核心操作。

三、Dijkstra 算法（非负边权专用）

1. 适用条件

图中所有边权 ，效率最高。

2. 算法思想

每次选出当前距离起点最近、且未确定最短路的节点，用该节点对相邻边做松弛，逐步确定所有点的最短路。

3. 算法流程

1. 初始化 数组，，其余为无穷大；
2. 使用优先队列（小根堆）维护 (距离, 节点)；
3. 取出堆顶节点 ，若已确定最短路则跳过；
4. 遍历 所有出边 ，执行松弛操作；
5. 松弛成功则将新状态压入优先队列；
6. 队列为空时算法结束。

4. 复杂度分析

• 堆优化版：