We are given a weighted directed graph G = (V, E, w). (The weights represent wid
ID: 3594845 • Letter: W
Question
We are given a weighted directed graph G = (V, E, w). (The weights represent widths of roads in a road network.) The width of a path P is the minimum of the weights of edges in P. (Intuitively, the width of a path is the maximum width of an object that can be transported on that path without the object ever ”sticking out”.) Given two vertices s, t we want to compute the widest path from s to t. Give an algorithm for the problem; your algorithm should be as fast as possible; state the running time of your algorithm.
Explanation / Answer
Steps:-
The algorithm that I am proposing is quite analogous to Dijkstra algorithm.
Initially we assigning label to each vertex v i.e. L[v] to minus infinity and starting vertex s is assigned the label plus infinity. Here lebel of node denotes the widest path to it from the starting node.
Each node based on its label value is stored in max-heap H with root node contain the node with highest label.
Every time I will delete the highest label vextex say u from max-heap H and to all the neighbors of u say v, we assigned the label based on formula L[v]=max(L[v], min(L[u],w(u,v))). Which means, label of vertex v will be maximum of its previous label and mimimum of label of u and path width from u to v. This is very interesting. Updated L[v] will have widest path discovered till v starting from vertex s.
After all the neighbors v label has been updated, we will increase their priority in max-heap(H), so that root node will be vextex of maximum label.
Thus iteratively this algorithm will assign the labels to all the vertices in v. So for all v, L[v] is the widest path from vertex s to vertex v. At the end we will return L[t] as out answer.
Following is the algorithm
Algorithm(G=(V,E,W),s,t)
1. For all v in V, L[v]=-infinity, L[s]= infinity, H.inset(v,L[v]) //initialize labels of all node to minus infinity and starting node s to infinity
2. While !H.empty() do{ //Till the max heap H is not empty
3. u=H.deletemax() //delete the element from H with maximum label
4. for all v in adj[u] do{ //for all the neighbors w of v do
5. L[v]=max(L[v], min(L[u],w(u,v))) //update the label of v
6. H.incprio(v,d[v]) //increase the priority of vertex v in max-heap H
7. } //end of while loop
8. Return L[t] //L[t] contain widest path from starting node s to node v
Complexity:- This algorithm is similar in run with dijkstra algorithm except that label updation equation is different and instead of min-heap in dijkstra we are using max-heap. So complexity is O(E log V)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.