企业官网建设流程全解析

📘 教案 19：最短路径问题与三类基本算法

一、问题定义

设有一张图 ( G = (V, E) )，其中：

• ( V )：顶点集合
• ( E )：边集合
• 每条边 ( (u, v) ) 具有权重 ( w(u, v) \in \mathbb{R} )

给定源点 ( s \in V )，定义从 ( s ) 到任意顶点 ( v ) 的路径长度为：

[len(s→v)=∑w(e)][ \text{len}(s \to v) = \sum w(e) ][len(s→v)=∑w(e)]

最短路径问题是：

对所有 ( v \in V )，求从 ( s ) 到 ( v ) 的最小路径长度

二、基本概念

1. 路径（Path）

从顶点序列：

[s=v0→v1→⋯→vk=v][ s = v_0 \to v_1 \to \cdots \to v_k = v ][s=v0​→v1​→⋯→vk​=v]

称为从 ( s ) 到 ( v ) 的路径。

2. 路径长度（Path Weight）

路径长度定义为：

[∑i=0k−1w(vi,vi+1)][ \sum_{i=0}^{k-1} w(v_i, v_{i+1}) ][∑i=0k−1​w(vi​,vi+1​)]

3. 最短路径（Shortest Path）

所有从 ( s ) 到 ( v ) 的路径中，长度最小者。

4. 负权边与负环

• 若存在 ( w(u,v) < 0 )，称为负权边
• 若存在环 ( C )，满足：

[∑e∈Cw(e)<0][ \sum_{e \in C} w(e) < 0 ][∑e∈C​w(e)<0]

称为负环

若存在负环，则最短路径问题无解（路径可无限减小）

三、问题分类依据

最短路径算法的选择完全由权重性质决定：

情况一：无权图或等权图

[w(u,v)=c(常数)][ w(u,v) = c \quad (\text{常数}) ][w(u,v)=c(常数)]

情况二：非负权图

[w(u,v)≥0][ w(u,v) \ge 0 ][w(u,v)≥0]

情况三：含负权边

[∃(u,v):w(u,v)<0][ \exists (u,v): w(u,v) < 0 ][∃(u,v):w(u,v)<0]

四、算法一：广度优先搜索（BFS）

适用条件

[∀(u,v),;w(u,v)=1][ \forall (u,v), ; w(u,v) = 1 ][∀(u,v),;w(u,v)=1]

基本思想

按路径长度（步数）逐层扩展：

• 第 (k) 层表示距离为 (k)

正确性说明

由于每条边权相同：

[路径长度=边数][ \text{路径长度} = \text{边数} ][路径长度=边数]

BFS 按层遍历：

第一次访问某顶点时，所用路径边数最少

时间复杂度

[O(V+E)][ O(V + E) ][O(V+E)]

五、算法二：Dijkstra 算法

适用条件

[∀(u,v),;w(u,v)≥0][ \forall (u,v), ; w(u,v) \ge 0 ][∀(u,v),;w(u,v)≥0]

核心思想（贪心策略）

维护集合 ( S )，表示已确定最短路径的节点。

每一步：

从未确定节点中选取当前距离最小者加入 ( S )

算法过程

设：

[dist[v]=当前已知最短距离][ dist[v] = \text{当前已知最短距离} ][dist[v]=当前已知最短距离]

初始化：

[dist[s]=0,dist[v]=∞][ dist[s] = 0, \quad dist[v] = \infty ][dist[s]=0,dist[v]=∞]

迭代：

[dist[v]=min⁡(dist[v],dist[u]+w(u,v))][ dist[v] = \min(dist[v], dist[u] + w(u,v)) ][dist[v]=min(dist[v],dist[u]+w(u,v))]

正确性关键（必须理解）

设当前选中节点为 ( u )，则：

[dist[u]=δ(s,u)][ dist[u] = \delta(s, u) ][dist[u]=δ(s,u)]

成立的原因：

• 所有边权非负
• 任何通过其他路径到达 ( u ) 的路径必然更长

时间复杂度

• 普通实现：(O(V^2))
• 堆优化：

[O((V+E)log⁡V)][ O((V + E)\log V) ][O((V+E)logV)]

六、算法三：Bellman–Ford 算法

适用条件

允许：

[w(u,v)<0][ w(u,v) < 0 ][w(u,v)<0]

核心思想

通过反复“松弛（relaxation）”边来逼近最优解：

[dist[v]=min⁡(dist[v],dist[u]+w(u,v))][ dist[v] = \min(dist[v], dist[u] + w(u,v)) ][dist[v]=min(dist[v],dist[u]+w(u,v))]

关键性质

最短路径最多包含：

[∣V∣−1][ |V| - 1 ][∣V∣−1]

条边

算法过程

重复：

[∣V∣−1 次][ |V| - 1 \text{ 次} ][∣V∣−1次]

对所有边执行松弛操作

负环检测

若第 ( |V| ) 次仍可松弛：

[⇒存在负环][ \Rightarrow \text{存在负环} ][⇒存在负环]

时间复杂度

[O(VE)][ O(VE) ][O(VE)]

七、三种算法对比

八、统一理解

三类算法本质区别在于：

如何选择下一次“扩展”的节点

• BFS：按层扩展（等代价）
• Dijkstra：按当前最小距离扩展（贪心）
• Bellman-Ford：不做选择，穷尽所有可能（动态规划式迭代）

九、总结性表述（规范表达）

最短路径问题是在带权图中，通过对路径代价的累加与比较，确定从源点到各节点的最小代价路径。不同算法的选择依赖于边权的结构特性，其核心差异体现在状态扩展策略与最优性保证条件上。