I have now read (and tried to understand) the similar question from Andrew Sutton with respect to Dijkstra's SP: <http://lists.boost.org/Archives/boost/2011/06/182381.php>
(On a slightly unrelated note, I first also used his way to call "update", but that totally killed the performance (and compare count) of fibonacci_heap. I would suggest to remove this form of "update" at least from fibonacci_heap, and require calling "increase" or "decrease" when you have modified the priority "manually".)
That's only a viable solution if you have some a priori knowledge about which "direction" the value has changed with respect to the comparison operator. If you have an expression like this:
x' = x + y;
where x is the previous key and x' the new key--a possible implementation of edge relaxation. You still have to compare x and x' to determine which direction the change was in. Minimally, you'd have to check y to determine if it was less than 0, assuming the types of x, x', and y are numeric.
Removing the update() method makes the user work harder. Increase and decrease are nice when you know that you can optimize.
btw, the fibonacci heap also provides an update_lazy with slightly different performance characteristics than update(), since it does not run a consolidation phase ... it mainly gives a better throughput at the costs of a worse worst-case performance ... tim