# 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

## closed as unclear what you're asking by D.W.♦, András Salamon, frafl, Raphael♦Jan 19 '14 at 2:13

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• 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).