Question

In the shortest-path algorithm we are concerned with the total length of the path between a source and every other node. Suppose instead that we are concerned with the length of the longest edge between the source and every node. That is, the bottleneck of a path is defined to be the length of the longest edge in the path. Design an efficient algorithm to solve the single source smallest bottleneck problem; i.e. find the paths from a source to every other node such that each path has the smallest possible bottleneck.

Answer 1

Dear Student, I have spent a lot of time in making these terms short and clean, so if you got something from it, then give it an Upvote. Thank You.

Design: The primary observation is that for any given distance d, all vertices of distance d or less from s are exactly those reachable from s along the subgraph of all edges of weight not greater than d.

Thus we seek to compute the distance to vertices in increasing order of distance and clearly, it suffices to examine the weights of the edges as every distance will correspond to one of these E values.

We maintain a heap such that at the start of each iteration the following inductive invariant is true: If the smallest edge in the heap has weight d, then every vertex of distance less than d has been found, and all the edges of weight d-or-more whose source is one of these vertices are in the heap

In an iteration of the algorithm, we extract the next minimum edge, determine all the vertices that can be reached through that edge along edges of the equal or lesser score, and update the induction.

Pseudo-code formulation:

procedure Search(v: vertex, d: weight)
{
D[v] <-- d
for v --> u in E do
if w(v --> u) <= d and D[u] = 1 then
Search(u,d)
else
   Add v --> u to Heap
}

D[v] <-- infinity for all v
D[s] <-- 0
Heap {s --> v}
while Heap !enpty do
{
e(= v --> u) <-- extract min Heap
if D[u] = 1 then
Search(u,w(e))
}

Worst-case time Complexity: An edge is added to the heap only if its source has just been assigned its distance (if then).

Therefore each edge is added to the heap at most once. Moreover, Search is only called when a vertex is about to be assigned it and so is not called more than V times. The algorithm is thus O(ElogV) in the worst case.