The following is my algorithm for finding bottle-neck path by sub-ranges searching. Actually I just want to get the smallest set that containing the widest path from s to t.
In the algorithm, searching is for the subset that contains path from s to t. The steps make sure the smallest edge in the result subset belongs to the widest path from s to t.
Suppose variables as the following.
$m$ -- the number of total edges.
$E_i$ -- the set which does not contain path from s to t at the $i_{th}$, while for all edges in $E_i$, the weight is bigger than or equal to the maximum minimum-weight edge in all s-t paths. $E_0$ is empty.
$T_i$ -- the set which is a sub-range that contain the maximum minimum-weight edge. We need to partition it into sub-ranges.
$k_i$ -- the number of sub-ranges at the $i_{th}$ recursion. It’s calculated out in Step 1.
Steps.
Step 1 - If $Size(T_i) = 1$ then the algorithm stops. Else $k_i = f(Size(T_i))$.
$f(Size(T_i))$ is a function whose argument is $Size(T_i)$. I am not sure what it should be.
Step 2 - Partition $T_i$ into $k_i$ descending sub-ranges. We use $R_j$ to stand for the $j_{th}$ sub-range whose weight of edges are only smaller than the ones in $j-1$ sub-ranges before it.
Partition is done by Fibonacci Heap. We don't need edges in one sub-set keep in order.
Step 3 - Let $Total = E_i$.
Step 4 - Repeat. Get sub-range $R_j$ from $k_i$ sub-ranges in descending order. ($k_i$ times at most)
- $Total = Total + R_j$
If there is a path from s to t in $Total$(its cost is $O(m)$),
we know that $Total$ contains the biggest minimum-weight edge.
- $E_{i+1} = Total - R_j$.
$T_{i+1} = R_j$.
In the next recursion, $R_j$ is partitioned to find a smaller set which containing the maximum minimum-weight edge.
Go to Step 1.
Recursively increase $E_i$, and decrease $T_i$ and $k_i$. Until the $Size(T_i) = 1$.
After the algorithm stops, we get the target set $E_{i_{max}}$ containing all the edges which are bigger than or equal to the maximum minimum-weight edge. So the widest path from s to t is in $E_{i-{max}}$.
If set $f(Size(T_i)) = Size(T_i)/2$, on average, the final recursion time will be $i_{max} = log_2 m$.
My question is that there should be a better $f(Size(T_i))$, what is it? And how to figure it out?