I'm taking an online algorithms class from Stanford, and one of the questions is as follows:
Define the bottleneck of a path to be the maximum length of one of its edges. A minimum-bottleneck path between two vertices s and t is a path with bottleneck no larger than that of any other s-t path. Suppose now that the graph is undirected. Give a linear-time (O(m)) algorithm to compute a minimum-bottleneck path between two given vertices.
Solving this with a modified Dijkstra's algorithm runs in O(mlog(n)) that doesn't meet the requirement. Wikipedia claims that there
exists a linear time algorithm for finding a widest s-t path in an undirected graph, that does not use the maximum spanning tree. The main idea of the algorithm is to apply the linear-time path-finding algorithm to the median edge weight in the graph, and then either to delete all smaller edges or contract all larger edges according to whether a path does or does not exist, and recurse in the resulting smaller graph.
There are couple of problems. The algorithm is mostly hand-waving, and I'm not looking for the widest path, but the opposite.
This paper has more text than Wikipedia, but it too, doesn't go into the gory details, especially when it comes to contracting the edges.
I've chalked out the following pseudocode:
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*)
Few things I don't understand:
OP here. A detail solution is found on my blog, but the pseudocode is as follows:
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*)