Widest Path

Question

Given a weighted (undirected) graph $G(V, E)$, the weight of an edge is called the width of the edge. The width of a path is defined to be the smallest weight among all edges on the path. (An edge with the smallest weight is called the bottle neck edge) For example, in the following graph, the path <$a, b, e, g$> has width 7.

A path $P(u, v)$ is called the widest if the width of the path is the largest among all paths from $u$ to $v$. For example, in the above figure, the widest path between vertex $a$ and vertex $g$ is <$a, b, c, d, f, g$> whose width is 8. Please modify Dijkstra’s algorithm to compute the widest path from a given vertex $s ∈ V$ to every other vertex.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Dijkstra_Widest_path(G, s,t):
    Q = ∅       # create priority queue
    width[s] = ∞
    for each vertex v in G: 
        if v != s :
            width[v] = -∞  
        π(v) = nil
        Q.enqueue(width[v])    # set all vertices in Q

    While Q not empty:
        u ← extractMax(Q)
        for each neighbor v of u:
            alt = max(width[v], min(width[u], w(u, v)))
            if alt > width[v]:                                
               width[v] = alt 
               π(v) = u 
               Q.increase-key(v, alt)  # updating a key within a max-heap

    # retrieve the path from s to t
    Stack S = ∅             # create a stack
    Push (S, t)
    v ← Top(S)
    while  π(v) != nil 
        Push (S, π(v))
        v = π(v)
    return S      # the path is stored in the stack S
                  # from top to bottom. 
End