# For Djikstra's algorithm, why are we surely done if we update all edges $|V|-1$ times?

Apparently, if we use Djikstra's algorithm to find the shortest path between the root node and all other nodes in a weighted graph with no negative cycles, we are done after updating the distance of each node $|V| - 1$ times.

This puzzles me because I think that a single round of breadth first search is enough. Why must we do $|V| - 1$ of these searches?

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.
• Thanks, what's the intuition behind why each neighboring node of the root may be updated a max of $|V| - 1$ times in a single round of BFS with a min heap? Jun 9, 2013 at 19:01
• $|V|-1$ is the absolute maximum, since each vertex is removed from the queue exactly once. A vertex can only be updated after/when it's discovered, so it has to be discovered early to reach $|V|-1$ updates (including the first from $\infty$ to some finite value). Assume $v$ is the root and $w$ its neighbor (weight $3|V|$). If we discover vertices with distance $i$ to $v$ and direct edge to $w$ with weight $3|V|-2i$. Then $w$s distance is reduced with every discovered vertex. Jun 9, 2013 at 19:17