1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I can add an example where so many updates happen, if this is needed. $\endgroup$ – frafl Jun 9 '13 at 14:38
  • $\begingroup$ 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? $\endgroup$ – David Faux Jun 9 '13 at 19:01
  • $\begingroup$ $|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. $\endgroup$ – frafl Jun 9 '13 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.