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