算法-最短路径：DAG、Dijkstra、Bellman-Ford

1. 最短路径 —— DAG

1.1. 前置条件

• 图必须是有向无环图（DAG）。

1.2. 基本原理

DAG上一定存在拓扑排序，且若在有向图 G 中从顶点 u -> v有一条路径，则在拓扑排序中顶点 u 一定在顶点 v 之前，而因为在DAG图中没有环，所以按照DAG图的拓扑排序进行序列最短路径的更新，一定能求出最短路径。

1.3. 代码示例

题目：给定几个带点权有向无环图，选一条从入度为0的起点走到出度为0的终点的路径，使得路径上的点权和最小。

分析：

• 首先点权图转边权图；
• 直接对每条边赋值，值为终点的点权值；
• 没有入度的点，添加一个顶点，连接一条有向边，使之边权等于该点点权。

1.4. 特性分析

• 时间复杂度：O(n+m)；

2. 最短路径 —— Dijkstra 算法

2.1. 前置条件

• 所有边的权重一定是非负的；
• 图中可以包含环；

2.2. 基本思路

(1) 找出“最便宜”的节点，即可在最短时间内到达的节点。

(2) 更新该节点对应的邻居节点的开销。

(3) 重复这个过程，直到对图中的每个节点都这样做了。

(4) 计算最终路径。

2.3. 程序代码

2.4. 动画展示

2.5. 特性分析

• 时间复杂度：O(n^2)；

3. 最短路径 —— Bellman-Ford 算法

3.1. 前置条件

• 单源最短路径(从源点s到其它所有顶点v)；
• 边权可正可负；
• 图中可以包含环；
• 可以判定是否具有负权重和环；

3.2. 基本思路

• 将除源点外的所有顶点的最短距离估计值 d[v] <-- ∞, d[s] <-- 0;
• 反复对边集 E 中的每条边进行松弛操作，使得顶点集V中的每个顶点 v 的最短距离估计值逐步逼近其最短距离（运行|v|-1次）；

3.3. 程序代码

3.4. 特性分析

• 时间复杂度：O(nm)