Running Time

The lowest quality heuristic is h(v) = 0. What algorithm is this?

Therefore, we get at least O(|V|²) or $O(\vert E\vert \log \vert V\vert)$, maybe better.