我正在斯坦福大学上一堂在线算法课，其中一个问题如下：
将路径的瓶颈定义为其边缘。两个顶点s和t之间的最小瓶颈路径是瓶颈不大于任何其他s-t路径的瓶颈的路径。现在假设图是无向的。给出线性时间(O(m((计算两个给定路径之间最小瓶颈路径的算法顶点。
使用不满足要求的O(mlog(n((中运行的修改Dijkstra算法来解决此问题。维基百科声称有
存在一种线性时间算法，用于在无向图，它不使用最大生成树。这个该算法的主要思想是应用线性时间路径查找算法将图中的中值边缘权重，然后根据删除所有较小的边或收缩所有较大的边路径是否存在，并在结果中递归较小的图形。
有几个问题。算法主要是挥手，我不是在寻找最宽的路径，而是相反的路径。
这篇论文的文本比维基百科多，但它也没有涉及血腥的细节，尤其是在收缩边缘时。
我已经写出了以下伪代码：
1: MBP(G, s, t)
2: if |E| == 1
3: return the only edge
4: else
5: x = median of all edge weights
6: E' = E - (v, w) where weight(v, w) < x
7: construct G'(V, E')
8: exists = is there a path from s to t in G'
9: if (exists == FALSE)
10: compute all the connected components Cᵢ of G'
11: reinsert the edges deleted into G'
12: G* = G'
13: for each Cᵢ
14: G* = SHRINK(G*, Cᵢ)
15: return MBP(G', s, t)
16: SHRINK(G, C)
17: leader = leader vertex of C
18: V* = {V(G) - C} ∪ {leader}
19: E* = {}
20: for each edge (v, w) ∈ E(G)
21: if v, w ∈ V*
22: E* = E* ∪ {(v, w, weight(v, w))}
23: else if v ∈ C, w ∈ V*
24: E* = E* ∪ {(leader, w, max(weight(v, w)))}
25: return G*(V*, E*)
有几件事我不明白：
- 第6行：删除权重高于或低于中值的边有什么关系
- 第20行：有3种类型的边，即在连接组件外部同时具有两个顶点的边、在连接组件中同时具有两种顶点的边，以及在连接组件内具有一个顶点并具有一个外顶点的边。第一种类型保留其边权重，第二种类型变为自循环，应删除(？(。第三种类型的边缘权重应该是多少
OP此处。在我的博客上找到了一个详细的解决方案，但伪代码如下：
1: CRITICAL-EDGE(G, s, t)
2: if |E(G)| == 1
3: return the only edge
4: else
5: x = median of all edge weights
6: X = E - (v, w) s.t. weight(v, w) > x
7: G' = G(V, X)
8: exists = is there a path from s to t in G'
9: if (exists == FALSE)
10: C = {C₁, C₂, ..., Cₖ} s.t. Cᵢ is a connected component of G
11: G' = G(V, E - X)
12: for i = 1 to |C|
13: G' = SHRINK(G', C, i)
14: else if X == E // no edges were deleted
15: X = {(v, w)} s.t. weight(v, w) = x
16: G' = G(V, X)
17: return CRITICAL-EDGE(G', s, t)
18: SHRINK(G, C, i)
19: leaderᵢ = leader vertex of C[i]
20: V* = {V(G) - C[i]} ∪ {leaderᵢ}
21: E* = {}
22: for each (v, w) ∈ E(G)
23: if v ∈ C[i], w ∈ C[j]
24: E* = E* ∪ {(leaderᵢ, leaderⱼ, min(weight(u, w)))} ∀ u ∈ C[i]
25: else if v, w ∉ C[i]
E * = E* ∪ {(v, w, weight(v, w))}
26: return G*(V*, E*)