每天学一个算法--最短路径问题与三类基本算法

教案 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从顶点序列[sv0→v1→⋯→vkv][ s v_0 \to v_1 \to \cdots \to v_k v ][sv0​→v1​→⋯→vk​v]称为从 ( s ) 到 ( v ) 的路径。2. 路径长度Path Weight路径长度定义为[∑i0k−1w(vi,vi1)][ \sum_{i0}^{k-1} w(v_i, v_{i1}) ][∑i0k−1​w(vi​,vi1​)]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(VE)][ O(V E) ][O(VE)]五、算法二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((VE)log⁡V)][ O((V E)\log V) ][O((VE)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等权图层级扩展(O(VE))Dijkstra非负权贪心选择(O((VE)\log V))Bellman-Ford有负权全局松弛(O(VE))八、统一理解三类算法本质区别在于如何选择下一次“扩展”的节点BFS按层扩展等代价Dijkstra按当前最小距离扩展贪心Bellman-Ford不做选择穷尽所有可能动态规划式迭代九、总结性表述规范表达最短路径问题是在带权图中通过对路径代价的累加与比较确定从源点到各节点的最小代价路径。不同算法的选择依赖于边权的结构特性其核心差异体现在状态扩展策略与最优性保证条件上。