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