# Widest path algorithm steps [closed]

I need to compute the bottleneck shortest paths from s to all vertices of a graph by modifying the Dijkstra’s algorithm. I found this explanation on Wikipedia(Link to Wikipedia) but I would appreciate if you can elaborate it a bit for me.

If the edges are sorted by their weights, then a modified version of Dijkstra's algorithm can compute the bottlenecks between a designated start vertex and every other vertex in the graph, in linear time. The key idea behind the speedup over a conventional version of Dijkstra's algorithm is that the sequence of bottleneck distances to each vertex, in the order that the vertices are considered by this algorithm, is a monotonic subsequence of the sorted sequence of edge weights; therefore, the priority queue of Dijkstra's algorithm can be replaced by an array indexed by the numbers from 1 to m (the number of edges in the graph), where array cell i contains the vertices whose bottleneck distance is the weight of the edge with position i in the sorted order. This method allows the widest path problem to be solved as quickly as sorting; for instance, if the edge weights are represented as integers, then the time bounds for integer sorting a list of m integers would apply also to this problem

So I need to sort my vertex by weight starting from A? I would appreciate if you can explain me the steps in this algorithm.

Thanks

• What is your question, precisely? What don't you understand? Did you try to apply this idea to a small example (a small graph with 4 or 5 vertices), by hand? What have you done, to understand this on your own? Also, you should cite the source of this quotation (always provide proper attribution when copying content from elsewhere). – D.W. Dec 2 '13 at 4:21
• AFIK wikipedia does not require proper citation, but I did mention that it is from Wiki. How would you cite wiki? My problem is that with my level of english I am having trouble understanding the steps that are needed to solve the problem. – user2067051 Dec 2 '13 at 4:37
• Sorry, did not know that. I have added the link and proper name, hopefully this works. Though I assumed that wikipedia does not have a copyright on their material.(Not arguing with you, just interesting side topic) – user2067051 Dec 2 '13 at 6:04
• Thanks for trying to understand the site rules, user2067051! Yes, we require attribution. As it happens, this has nothing to do with copyright; we require attribution of the source, regardless of whether the source material is copyrighted or not. We just believe in giving credit to the original source (and as a small bonus, sometimes having a link to the original source provides additional context that helps understand the question better). I appreciate your desire to learn the site policies. – D.W. Dec 2 '13 at 6:15

The way to use Dijkstra's algorithm to solve the $s$-to-$t$ widest-path problem (in a directed graph) is described well in the following lecture notes:
Make sure to read Sections 13.1, 13.2, and 13.3. You will see that a single-line change to Dijkstra's algorithm suffices (we change the $+$ to $\min$, and change the $\min$ to $\max$, to represent the fact that we now have a different metric for the "goodness" of a path).