For Djikstra's algorithm, why are we surely done if we update all edges $|V|-1$ times?
Either you mixed up two algorithms or you misinterpreted an upper bound. One level of a BFS with priority queue is enough, but during this one round a neighbor of the root may be updated $|V|-1$ times, therefore the update operation needs to be efficient.