Dijkstra 算法
Dijkstra 算法
- 前提：图中没有负权边 (non-negative weights)
- 可以解决单源最短路径问题，即求解从起始点到其他点的最短距离和对应路径
- 基于性质：一旦某个点的最短路径被确定，它就不会再变小
- 初始化：对于所有非起点的节点，将其 dist 设为 +∞. 对起点设为 0.
- 贪心选择：
- 每一步从所有尚未确定最短距离的节点中，选择当前距离起点最近的节点，将其最短距离确定；
- 然后用该节点去松弛（relax）其邻居的距离（即尝试更新最短距离）。
- 重复该过程，直到所有可达节点的最短距离被确定。
- 时间复杂度为 O(V2)，可以通过最小堆优化到 O(ElogV)
例子：
DijkstraExample距离矩阵更新：
step012345678pivot−ACEDFHGBA000000000B∞88866666C∞11111111D∞∞3333333E∞∞2222222F∞∞∞333333G∞∞∞∞66555H∞∞∞∞∞4444前驱矩阵更新（用于求解最短距离对应路径）：
step012345678pivot−ACEDFHGBA−−−−−−−−−B−AAADDDDDC−AAAAAAAAD−−CCCCCCCE−−CCCCCCCF−−−EEEEEEG−−−−DDHHHH−−−−−FFFFDAG 最短路径
Bellman 算法
- 前提：有向无环图（DAG）
- 可以解决单源最短路径问题，即求解从起始点到其他点的最短距离和对应路径
- 基于性质：每个点的最短距离等于所有【前驱点的最短距离+当前边权】之和的最小值。由于 DAG 中没有环，因此一定存在一个拓扑序使得对于计算点 v 时，所有其可能的前驱 u 都被计算完成。
- 先进行拓扑排序：不断选择入度为 0 的点，删除其出边，更新其他点入度，直到所有点完成排序
- 按照拓扑排序遍历：
- 初始化起点距离 dist[s]=0 和所有其他点 dist[v]=+∞
- 时间复杂度： O(V+E)，因为每个点和每条边都只被处理一次
根据图，可以得到拓扑排序过程（当入度为 0 的点数量不为 1 时，按照字母排序优先处理较小排序的节点）：
| step | 当前入度为 0 的点 | 删除的边 | 更新入度 |
|---|
| 1 | A | A→C, A→D, A→B | C:1→0, D:2→1, B:3→2 |
| 2 | C | C→E, C→F | E:1→0, F:2→1 |
| 3 | E | E→D, E→F | D:1→0, F:1→0 |
| 4 | D | D→G, D→B | G:2→1, B:2→1 |
| 5 | F | F→H | H:1→0 |
| 6 | H | H→G | G:1→0 |
| 7 | G | G→B | B:1→0 |
| 8 | B | 无 | 无 |
最终得到一个合法拓扑序：
A, C, E, D, F, H, G, B因此从源点 A 出发的距离矩阵和前序矩阵分别为：
step012345678pivot−ACEDFHGBA000000000C∞44444444E∞∞2222222D∞77333333F∞∞9555555H∞∞∞∞∞4444G∞∞∞∞55111B∞10101077733 step012345678pivot−ACEDFHGBA−−−−−−−−−C−AAAAAAAAE−−CCCCCCCD−AAEEEEEEF−−CEEEEEEH−−−−−FFFFG−−−−DDHHHB−AAADDDGG需要注意的是如果想知道 DAG 的非源点（以 E 为源点为例）到其他点的距离，不修改拓扑序，直接从拓扑序里 E 为起点开始遍历，生成的的距离矩阵和前序矩阵分别为：
step012345678pivot−ACEDFHGBA∞∞∞∞∞∞∞∞∞C∞∞∞∞∞∞∞∞∞E000000000D∞∞∞111111F∞∞∞333333H∞∞∞∞∞2222G∞∞∞∞33−1−1−1B∞∞∞∞55511 step012345678pivot−ACEDFHGBA−−−−−−−−−C−−−−−−−−−E−−−−−−−−−D−−−EEEEEEF−−−EEEEEEH−−−−−FFFFG−−−−DDHHHB−−−−DDDGGRoy-Warshall-Floyd 算法
Roy-Warshall-Floyd 算法，也常称为 Floyd-Warshall 算法。
前提：图中允许存在负权边（negative edge），但不能存在负权环（negative cycle）
可以解决所有点对最短路径问题（All-Pairs Shortest Paths, APSP），即同时求解任意两个点之间的最短距离
基于动态规划递推：
- 子问题：在只允许 1,…,k 作为中间点的限制下，从 i 到 j 的最短距离是多少。
- 递推：之前已求解出来在 1,…,k−1 作为中间点的限制下从 i 到 j 的最短距离，基于此结果计算在 1,…,k−1,k 作为中间点的限制下从 i 到 j 的最短距离
- 形式化表述：设 dij(k) 表示从 i 到 j 的路径中，只允许使用 {1,…,k} 作为中间点时的最短距离。当新允许点 k 作为中间点时，最短路径只有两种可能：一种是不经过 k，此时距离仍为 dij(k−1)；另一种是经过 k，此时路径可以拆成 i→k 和 k→j 两段，距离为 dik(k−1)+dkj(k−1)。因此逐步放宽允许作为中间点的集合，有递推关系：
dij(k)=min(dij(k−1),dik(k−1)+dkj(k−1))初始化：若 i=j，则 d(i,j)=0. 若存在边 i→j，则 d(i,j)=w(i,j). 若不存在边，则初始化为 +∞
动态规划过程：依次枚举每个点 k，尝试让所有路径都允许经过 k，并且对所有点对 (i,j) 更新：
d(i,j)=min(d(i,j),d(i,k)+d(k,j))时间复杂度：
O(V3)因为需要三重循环枚举：中间点 k、起点 i 和终点 j
初始化距离矩阵：不允许经过任何中间点
D(0)=ABCDA0∞∞∞B30∞1C∞20∞D8∞40第一步：允许经过点 A。由于没有任何点能够到达 A，因此通过 A 无法产生更短路径。所以矩阵保持不变：
D(1)=D(0)=ABCDA0∞∞∞B30∞1C∞20∞D8∞40第二步：允许经过点 B。现在允许路径：∀(i,j)∈V2,i→B→j. 因为根据 D(1) 图里有 {a,d}→b→{c}，因此需要更新 a→c 和 d→c。更新后：
D(2)=ABCDA0∞∞∞B30∞1C5203D8∞40D(3)=ABCDA0∞∞∞B30∞1C5203D8640第四步：允许经过点 D。现在允许路径：∀(i,j)∈V2,i→D→j. 因为根据 D(2) 图里有 {a,b,c}→d→{b,c}，因此需要更新 a→b, a→c, b→c, c→b.
最终矩阵：
D(4)=ABCDA0∞∞∞B3051C5203D8640最终最短距离矩阵为 D=D(4).
前驱矩阵为：
P=ABCDA−−−−BA−DDCBB−BDACC−