Question

PRINCETON UNIVERSITY 12. Algorithm design. (8 points) Given an edge-weighted digraph G the bottleneck capacity of a path is the minimum weight of an edge on the path. For each part elow, give a crisp and concise English description of your algorithm in the space provided. Your ansuer will be graded on correctness, eficieney, clarity, and conciseness (a) Given an edge-weighted digraph G, two distinguished vertices s and t, and a threshold value T, design an algorithm to find any one path from s to t of bottleneck capacity greater than or equal to T or report that no such path exists. The order of growth of the worst case running time of your algorithm should be E+ V (b) Using the subroutine from (a), design an algorithm to find a marimum bottleneck capacity path from s to t in an edge-weighted digraph G. The order of growth of the worst case running time of your algorithm should be (E + V) log E

Answer 1

a. Algorithm is very simple. Since we are interested to find any path from s to t with bottleneck capacity at least T. This means that we are only interested to consider the edge whose weight is at least T, since no edge with weight less than T can be part of bottleneck edges.

ALGORITHM(G=(V,E),s,t)

1. For all the edges e in E:-

2........If(weight[e] < T)

3.............Remove edge e from graph G.

4. Perform Breadth First Search to get the path from s to t if it exist.

Above algorithm will return the path from s to t considering only the bottleneck edges if the path exist. Time complexity of this algorithm will be time complexity of Breadth First Search which will be O(V+E)

b. In order to find maximum bottleneck capacity path we will perform algorithm analogous to Dijkstra algorithm in which, dist[v] indicate maximum bottleneck capacity path from s to v. So our updation equation will be

if (dist[v] < min (dist[u] , weight(u,v)) then

dist[v] = min (dist[u] , weight(u,v)) and

parent[v] = u

The reason behind doing that is, if there exist path of more bottleneck capacity from s to v via u then we will accept that path.

Below is the algorithm:-

ALGORITHM(G=(V,E),s, t))

1. For all the vertices v in V:-

2...........dist[v] = 0; //This means initially bottleneck capacity from s to v is 0 till no path is explored.

3. dist[s] = INFINITY

4. For all the vertices v in V:-

5.........Q.enqueue(v) //Add into priority queue Q all the vertices, with maximum value of dist[v] have highest priority

6. While Q.notEmpty()

7........u = Q.dequeue() //Remove the highest priority node from Q

8........For all the vertices v adjacent to u:-

9...............If dist[v] < min (dist[u] ,weight(u,v))

10...................dist[v] = min (dist[u] ,weight(u,v))

11...................parent[v] = u;

12...................Q.modify(v , dist[v]) //Modify the priority of v in Q

13. Return dist // the array dist will hold the maximum bottleneck capacity path from s to every vertices

This algorithm will run with time complexity same as that of Dijkstra algorithm i.e. O((E+V) log E).

Please comment for any clarification.