You reckon the perfect information version is cheaper than an algorithm that works only on the tiles near to the unit? But this quickly gets too complicated to discuss; there's the confusing matter of precalculation versus live updating.
It's also why Brood War players got into the habit of spam-clicking, because the game would recompute paths every time you issued a command, so spam-clicking resulted in smoother movement.