2
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$
    – D.W. ♦
    Dec 2, 2013 at 4:21
  • $\begingroup$ 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. $\endgroup$
    – user2067051
    Dec 2, 2013 at 4:37
  • $\begingroup$ 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) $\endgroup$
    – user2067051
    Dec 2, 2013 at 6:04
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Dec 2, 2013 at 6:15

1 Answer 1

Reset to default
0
$\begingroup$

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:

http://www.cs.cmu.edu/~avrim/451f08/lectures/lect1007.pdf

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

The section you quoted from Wikipedia is talking about a small optimization to this variant of Dijkstra's algorithm. However, you can use the variant of Dijkstra's algorithm in Section 13.3 of those lecture notes directly, without the optimization mentioned in Wikipedia, if you like -- and that's easier to understand.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for explanation, I think I am finally getting it. So I basically need to the path that has the largest min edge? $\endgroup$
    – user2067051
    Dec 2, 2013 at 6:39
  • $\begingroup$ @user2067051, yes, that's the definition of the widest-path problem (see the top of the Wikipedia article you linked to, or the lecture notes I referred to). $\endgroup$
    – D.W. ♦
    Dec 2, 2013 at 6:43
  • $\begingroup$ Thanks! Would this example also cover the negative weights case? The it says that it won't work for dijkstra's algorithms if there is a negative weight. $\endgroup$
    – user2067051
    Dec 2, 2013 at 7:05
  • $\begingroup$ @user2067051, for this application (widest paths), negative weight edges are actually OK (even though they are indeed a problem for the normal shortest paths case). You can try it out on some small examples, or better yet, try modifying the standard proof of correctness for Dijkstra's algorithm to show that the algorithm works correctly. P.S. This site isn't really very good for repeated follow-up questions. It is intended for one question and one answer. So, make sure you phrase your original question carefully to ask what you want to know, so you won't need follow-up questions! $\endgroup$
    – D.W. ♦
    Dec 2, 2013 at 7:17

Not the answer you're looking for? Browse other questions tagged or ask your own question.