> Are we talking about Dijkstra's graph traversal algorithm? > If so, there is no need to increase/decrease anything.
Implementing Dijkstra's shortest path algorithm actually requires to decrease the priority of some nodes. But this does not mean your priority queue data structure has to support such an operation. When you consider the edge x->y, x being the node you just extracted from the priority queue, you might just have discovered a better path to y and thus you have to update the priority associated to x. When there is indeed such an improvement, you have two options: - either your priority queue data structure provides a decrease_key operation, and then you use it; this is the case with Fibonacci heaps, an imperative data structures which provides decrease_key in O(1) and thus makes Dijkstra's algorithm complexity O(V log(V) + E). - or your priority queue does not provide such an operation, and you simply add another entry for y in the priority queue, with a different key. It means you have now several entries for y in the priority queue. The better will be extracted first; the others will be ignored when they are extracted later. Complexity is now O(E log(V)). In practice, solution 2 in fast enough. This is what is implemented in Ocamlgraph(using heaps I mentioned earlier). See chapter 25 in the Cormen, for instance. -- Jean-Christophe -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
