目录
最短路径问题
背景
-
交通路线图：
- 顶点：城市
- 边：城市之间的交通路线
-
从城市 v 0 v_0 v0 出发到达其他城市至少要经过几条路线？
-
从城市 v 0 v_0 v0 出发到达其他城市的最短路线有多长？
-
两顶点间可能存在多条路径
- 每条路径所经过的边数可能不同
- 每条路径上的各边权值之和可能不同
-
从一个指定顶点到达另一个指定顶点的路径上各边权值之和为最小的路径被称为最短路径，这类问题亦称为最短路径问题
-
单源最短路径
- 无权最短路径
- 正权最短路径
-
每对顶点之间的最短路径
无权最短路径问题
-
无权——所有边的权值都为 1
- 源点到各顶点的路径所经历的边的数目就是路径的长度
- 相对于源点由近及远依次求各顶点的最短路径
\begin{itemize}
-
记到达某个城市的路径条数为 D i D_i Di
-
从 v 0 v_0 v0 出发经过 0 条路径是 v 0 v_0 v0，可得 D 0 = 0 D_0 = 0 D0=0
-
从 v 0 v_0 v0 出发经过 1 条路径可到达 v 2 , v 5 v_2, v_5 v2,v5，可得 D 2 = D 5 = 1 D_2 = D_5 = 1 D2=D5=1
-
从 v 0 v_0 v0 出发经过 2 条路径可到达 v 1 , v 3 v_1, v_3 v1,v3，可得 D 1 = D 3 = 2 D_1 = D_3 = 2 D1=D3=2
-
从 v 0 v_0 v0 出发经过 3 条路径可到达 v 4 , v 6 v_4, v_6 v4,v6，可得 D 4 = D 6 = 3 D_4 = D_6 = 3 D4=D6=3
与图的广度优先搜索的顺序一致
-
对任意点 v i v_i vi，若 v i v_i vi 到点 s s s 的最短距离是 D i D_i Di，则它的邻居经过它到 s s s 的最短距离是 D i + 1 D_i + 1 Di+1
算法
算法思想
- D i D_i Di 为源点 s s s 到顶点 i i i 的最短路径长度：
- 初始化： D 0 = 0 D_0 = 0 D0=0, D i = − 1 D_i = -1 Di=−1
- 从初始顶点 s s s 开始进行广度优先遍历，对任意顶点 v i v_i vi，若 v i v_i vi 到点 s s s 的最短距离是它的上层邻居到 s s s 的最短距离是加 1
回顾广度优先遍历：维护一个队列和visited数组
- 将所有顶点的visited[]值置为 0，访问初始顶点 v 0 v_0 v0，置visited[ v 0 v_0 v0] = 1， v 0 v_0 v0 入队
- 检测队列是否为空，若队列为空，则算法结束
- 从队头取出一个顶点 v v v，检测其每个邻接顶点 w w w：
- 如果 w w w 未被访问过，则访问 w w w；将 visited[ w w w]值更新为 1；将 w w w 入队；
- 转步骤 ②
- 解决：
- 队列存放已得到最短路径值的顶点
- 采用邻接表存储图
- 两个数组}：
- dist[]：从源点到顶点 i i i 的最短路径长度
- path[]：从源点到顶点 i i i 的路径上最后一个经过的顶点，方便找到起点到这个结点的路径。
// SPath1 - 初始化
CREATEQ(Q); // 创建一个队列 Q
for (int i = 1; i <= n; i++) {
path[i] = -1; // 初始化路径数组，表示尚未访问的顶点
dist[i] = -1; // 初始化距离数组，表示尚未计算的距离
}
dist[v] = 0; // 起始顶点的距离为 0
Q.enqueue(v); // 起始顶点入队列
// SPath2 - 求从顶点到其他各顶点的最短路径
while (!Q.isEmpty()) { // 当队列不为空时
u = Q.dequeue(); // 队头顶点出队
p = adjacent(Head[u]); // 获取顶点 u 的邻接表头指针
// 遍历所有邻接顶点
while (p != NULL) {
k = VerAdj(p); // 获取邻接顶点
if (dist[k] == -1) { // 如果顶点 k 未被访问
Q.enqueue(k); // 顶点 k 入队
dist[k] = dist[u] + 1; // 更新顶点 k 的最短距离
path[k] = u; // 记录顶点 k 的前驱节点
}
p = p->link; // 继续访问下一个邻接顶点
}
}
时间复杂性
- 在最短路径的计算中，一个顶点入队出队各一次，时间复杂性为 O ( n ) O(n) O(n)，而对每个顶点，都要对它的边链表进行遍历，其遍历邻接表的开销为 O ( e ) O(e) O(e)，于是整个算法的时间复杂性为 O ( n + e ) O(n + e) O(n+e)
正权最短路径问题
- 广度优先策略不可行，最短路径不一定恰好就是连接这两个顶点的边（若此边存在），而可能就是一条包括一个或多个中间顶点的路径
迪杰斯特拉（Dijkstra）算法
-
从 S S S 出发到某个顶点 w w w 的最短距离 D w D_w Dw 可以拆分成 S S S 到中间结点 v v v 的距离和中间结点 v v v 到 w w w 的距离：}
D w = D v + weight ⟨ v , w ⟩ 中间结点可以为空： S 和 v 直接相连， D w = weight ⟨ S , w ⟩ D_w = D_v + \text{weight}\langle v, w \rangle \quad \text{中间结点可以为空：$S$ 和 $v$ 直接相连，$D_w = \text{weight}\langle S, w \rangle$} Dw=Dv+weight⟨v,w⟩中间结点可以为空：S 和 v 直接相连，Dw=weight⟨S,w⟩ -
经过中间结点 v v v 到达 w w w 的距离最短，则必须 S S S 出发到 v v v 也是走的最短路径 -> 用不同的中间结点的最短路径 D v D_v Dv 去测试哪个距离最短
-
问题：
- 确定中间结点：每次选一个距离最短的且没有做过中间结点的点
- 确定 S S S 到中间结点 v v v 的最短距离 D v D_v Dv
- 更新到 v v v 到 w w w 的邻居的最短距离
-
初始化时 (S 为初始顶点)， D S = 0 且 ∀ i ≠ S , D i = + ∞ D_S = 0 且 \forall i \neq S, \, D_i = +\infty DS=0且∀i=S,Di=+∞
-
dist 数组：表示当前找到的从源点 v 0 v_0 v0 到顶点 v i v_i vi 的最短路径的长度
- 初始化时若从源点 v 0 v_0 v0 到顶点 v i v_i vi 有边，则 dist[i] 为该边上的权值
- 若从源点 v 0 v_0 v0 到顶点 v i v_i vi 没有边，则 d i s t [ i ] = + ∞ dist[i] = +\infty dist[i]=+∞
-
path 数组：记录从源点 v 0 v_0 v0 到顶点 v i v_i vi 的最短路径上顶点 v i v_i vi 的前驱顶点号
-
visit 数组：记录顶点是否被选中成为中间结点
算法思路
初始化 ① 在未访问的顶点中选择 D v 最小的顶点 v ，访问 v ，令 visit [ v ] = 1. ② 依次考察 v 的邻接顶点 w ，若 D v + weight ⟨ v , w ⟩ < D w , 则改变 D w 的值，使 D w = D v + weight ⟨ v , w ⟩ . ③ 重复 ① 和 ②，直至所有顶点被访问。 \begin{aligned} &\textbf{初始化} \\[10pt] &① \, \text{在未访问的顶点中选择} \, D_v \, \text{最小的顶点} \, v，\text{访问} \, v，\text{令} \, \text{visit}[v] = 1. \\[10pt] &② \, \text{依次考察} \, v \, \text{的邻接顶点} \, w，\text{若} \\ &\quad D_v + \text{weight} \langle v, w \rangle < D_w, \\[10pt] &\quad \text{则改变} \, D_w \, \text{的值，使} \, D_w = D_v + \text{weight} \langle v, w \rangle. \\[10pt] &③ \, \text{重复} \, ① \, \text{和} \, ②，\text{直至所有顶点被访问。} \end{aligned} 初始化①在未访问的顶点中选择Dv最小的顶点v，访问v，令visit[v]=1.②依次考察v的邻接顶点w，若Dv+weight⟨v,w⟩<Dw,则改变Dw的值，使Dw=Dv+weight⟨v,w⟩.③重复①和②，直至所有顶点被访问。
伪代码
DSHortestPath(n, v)
// DSPath1 [初始化]
FOR i = 1 TO n DO
path[i] ← -1
dist[i] ← max // 初始化距离为最大值
visit[i] ← 0 // 记录顶点是否被访问
dist[v] ← 0 // 起始顶点 v 的距离设为 0
u ← v // u 表示将访问的顶点
visit[u] ← 1 // 标记顶点 u 为已访问
p ← adjacent(Head[u]) // 获取顶点 u 的邻接链表头指针
// DSPath2 [求从起始顶点到其他各顶点的最短路径]
FOR j = 1 TO n - 1 DO // 访问每个节点
WHILE p ≠ ∧ DO
k ← VerAdj(p)
IF s[k] ≠ 1 AND dist[u] + cost(p) < dist[k] THEN
dist[k] ← dist[u] + cost(p) // 更新邻接顶点的距离
path[k] ← u // 更新路径
p ← link(p) // 遍历下一个邻接节点
// 确定即将被访问的顶点
ldist ← max
FOR i = 1 TO n DO
IF (dist[i] > 0 AND dist[i] < ldist AND s[i] = 0) THEN
ldist ← dist[i]
u ← i // 确定未访问的且距离最小的顶点
s[u] ← 1 // 访问顶点 u
p ← adjacent(Head[u]) // 获取顶点 u 的邻接链表头指针
时间复杂度
O ( ∑ i = 1 n ( n + d i ) ) = O ( n 2 + ∑ i = 1 n d i ) = O ( n 2 + e ) O\left(\sum_{i=1}^n (n + d_i)\right) = O\left(n^2 + \sum_{i=1}^n d_i\right) = O(n^2 + e) O(∑i=1n(n+di))=O(n2+∑i=1ndi)=O(n2+e)
每对顶点之间的最短路径
-
问题的提出：
- 已知一个带权图，对每一对顶点 v i ≠ v j v_i \neq v_j vi=vj，计算出 v i v_i vi 与 v j v_j vj 之间的最短路径和最短路径长度
-
直接的思路：
- 以每个顶点为出发点多次调用 Dijkstra。
- 更新邻接矩阵：把每个顶点邻接的顶点关系放到邻接矩阵里面去依次比较，找最小的距离
-
定义一个 n n n 阶方阵序列： A ( − 1 ) , A ( 0 ) , … , A ( n − 1 ) A^{(-1)}, A^{(0)}, \dots, A^{(n-1)} A(−1),A(0),…,A(n−1)，其中：
A ( − 1 ) [ i ] [ j ] = Edge [ i ] [ j ] ; A^{(-1)}[i][j] = \text{Edge}[i][j]; A(−1)[i][j]=Edge[i][j];
A ( k ) [ i ] [ j ] = min { A ( k − 1 ) [ i ] [ j ] , A ( k − 1 ) [ i ] [ k ] + A ( k − 1 ) [ k ] [ j ] } k = 0 , 1 , … , n − 1 A^{(k)}[i][j] = \min \{ A^{(k-1)}[i][j], A^{(k-1)}[i][k] + A^{(k-1)}[k][j] \} k = 0, 1, \dots, n-1 A(k)[i][j]=min{A(k−1)[i][j],A(k−1)[i][k]+A(k−1)[k][j]}k=0,1,…,n−1.
A ( 0 ) [ i ] [ j ] A^{(0)}[i][j] A(0)[i][j] 是从顶点 v i v_i vi 到 v j v_j vj，中间顶点是 v 0 v_0 v0 的最短路径的长度，
A ( k ) [ i ] [ j ] A^{(k)}[i][j] A(k)[i][j] 是从顶点 v i v_i vi 到 v j v_j vj，中间顶点的序号不大于 k k k 的最短路径的长度，
A ( n − 1 ) [ i ] [ j ] A^{(n-1)}[i][j] A(n−1)[i][j] 是从顶点 v i v_i vi 到 v j v_j vj 的最短路径长度。 -
上式每迭代一次，从顶点到顶点之间的最短路径就多考虑一个中间顶点。经过 n n n 次迭代后， A ( k ) [ i ] [ j ] A^{(k)}[i][j] A(k)[i][j] 的值就是从顶点到顶点之间的最短路径长度
伪代码
// ALength1 [初始化]
FOR i = 1 TO n DO // 矩阵 A 和路径数组 path 初始化
FOR j = 1 TO n DO
A[i][j] ← Edge[i][j] // 初始化邻接矩阵 A，即 A^(0)
IF (i ≠ j AND A[i][j] < max) THEN
path[i][j] ← i // 如果 i 和 j 之间有边，记录路径前驱为 i
ELSE
path[i][j] ← -1 // 否则路径前驱为 -1
// ALength2 [求图中任意两顶点的最短路径]
FOR k = 1 TO n DO // 从 A^(0) 开始构造 A^(n-1)
FOR i = 1 TO n DO
IF (i ≠ k) THEN
FOR j = 1 TO n DO
IF (j ≠ k AND j ≠ i AND A[i][k] < max AND A[k][j] < max AND A[i][k] + A[k][j] < A[i][j]) THEN
A[i][j] ← A[i][k] + A[k][j] // 更新最短路径长度
path[i][j] ← k // 更新路径
最小支撑树
- 对于一个无向网络——无向加权连通图 N = ( V , E , C ) N=(V, E, C) N=(V,E,C)（ C C C 表示该图为权图），其顶点个数为 ∣ V ∣ = n |V| = n ∣V∣=n，图中边的个数为 ∣ E ∣ |E| ∣E∣，可以从它的 ∣ E ∣ |E| ∣E∣ 条边中选出 n − 1 n-1 n−1 条边，使之满足：
- 这 n − 1 n-1 n−1 条边和图的 n n n 个顶点构成一个连通图
- 该连通图的代价（ n − 1 n-1 n−1 条边上的权值之和）是所有满足条件 (1) 的连通图的代价的最小值。
- 这样的连通图被称为网络的最小支撑树（Minimum-cost Spanning Tree）
- 极大子图：无环路
- 最小子图：连通
普利姆(Prim)算法
- 设为 N = ( V , E , C ) N=(V, E, C) N=(V,E,C) 连通网， T E TE TE 是 N N N 的最小支撑树的边的集合
- 算法开始时， U = u 0 ( u 0 ∈ V ) U = {u_0} (u_0 \in V) U=u0(u0∈V), T E = ∅ TE = \emptyset TE=∅
- 找到满足
w e i g h t ( u , v ) = min w e i g h t ( u 1 , v 1 ) ∣ u 1 ∈ U , v 1 ∈ V − U weight(u, v) = \min{weight(u_1, v_1) \mid u_1 \in U, v_1 \in V-U} weight(u,v)=minweight(u1,v1)∣u1∈U,v1∈V−U 的边，把它并入集合 T E TE TE 中， v v v 同时并入 U U U - 反复执行步骤 ②，直至 U = V U = V U=V 时终止算法
伪代码
- 假设图用邻接矩阵存储。普里姆算法的实现需要两个辅助数组 c l o s e d g e [ n ] closedge[n] closedge[n] 和 T E [ n − 1 ] TE[n-1] TE[n−1]
- c l o s e d g e [ ] closedge[] closedge[] 之元素包括 L o w c o s t Lowcost Lowcost 和 V e x Vex Vex 两个域，定义如下：
若 v ∉ U v \notin U v∈/U，则 c l o s e d g e [ v ] . L o w c o s t = min w e i g h t ( u , v ) ∣ u ∈ U closedge[v].Lowcost = \min{weight(u, v) \mid u \in U} closedge[v].Lowcost=minweight(u,v)∣u∈U，
c l o s e d g e [ v ] . V e x = u , , u ∈ U closedge[v].Vex = u, , u \in U closedge[v].Vex=u,,u∈U
若 v ∈ U v \in U v∈U，则 c l o s e d g e [ v ] . L o w c o s t = 0 closedge[v].Lowcost = 0 closedge[v].Lowcost=0， c l o s e d g e [ v ] . V e x = − 1 closedge[v].Vex = -1 closedge[v].Vex=−1 - 数组 T E [ n − 1 ] TE[n-1] TE[n−1] 是最小支撑树的边集合，每个数组元素 T E [ i ] TE[i] TE[i] 表示一条边，
T E [ i ] TE[i] TE[i] 由 h e a d head head、 t a i l tail tail 和 c o s t cost cost 三个域构成，分别存放边的两个端点和权值。
\\ Prim1 [以顶点 1 为初始顶点，初始化数组 closedge]
FOR i = 1 TO n DO
Lowcost(closedge[i]) ← edge[1][i]; // 初始化最小权值
Vex(closedge[i]) ← 1; // 顶点 1 作为起始顶点进入集合 U
Vex(closedge[1]) ← -1; // 标记顶点 1 已进入集合 U
count ← 1; // 记录支撑树的边数
//Prim2 [构造图的最小支撑树]
FOR i = 2 TO n DO // 循环 n-1 次
v ← 0
min ← max // 设置最小值 min 为最大值
FOR j = 1 TO n DO // 寻找当前权值最小的边和该边的终点 v
IF (Vex(closedge[j]) ≠ -1 AND Lowcost(closedge[j]) < min) THEN
v ← j
min ← Lowcost(closedge[j])
IF v ≠ 0 THEN // 找到了最小的边
head(TE[count]) ← Vex(closedge[v]) // 存储最小边的起点
tail(TE[count]) ← v // 存储最小边的终点
cost(TE[count]) ← Lowcost(closedge[v]) // 存储最小边的权值
count ← count + 1 // 支撑树边计数器加 1
Lowcost(closedge[v]) ← 0 // 修改边权值为 0
Vex(closedge[v]) ← -1 // 标记顶点 v 已加入集合 U
// 因为 v 加入了集合 U，更新到集合 U 的最短距离
FOR j = 1 TO n DO
IF (Vex(closedge[j]) ≠ -1 AND edge[v][j] < Lowcost(closedge[j])) THEN
Lowcost(closedge[j]) ← edge[v][j] // 更新最短距离
Vex(closedge[j]) ← v // 更新终点信息
克鲁斯卡尔(Kruskal)算法
-
设连通网 N = ( V , E , C ) N=(V, E, C) N=(V,E,C)， T T T 为 N N N 的最小支撑树。初始时 T = V , ∅ T = {V, \emptyset} T=V,∅，即 T T T 中没有边，只有 n n n 个顶点就是 n n n 个连通分量。
- 在 E E E 中选择权值最小的边，并将此边从 E E E 中删除
- 如果此边的两个顶点在 T T T 的不同的连通分量中，则将此边加入到 T T T 中，从而导致 T T T 减少一个连通分量
- 如果此边的两个顶点在同一个连通分量中，则返回到步骤 1
- 循环以上操作直至 T T T 中仅剩一个连通分量时，终止操作
时间复杂度
- 普里姆（Prim）算法的时间复杂性为 O ( n 2 ) O(n^2) O(n2)，算法适于求边稠密网的最小支撑树。
- 正好相反，克鲁斯卡尔（Kruskal）算法适于求边稀疏网的最小支撑树，其时间复杂性为 O ( e log 2 e ) O(e \log_2 e) O(elog2e)