If I have an algorithm that fills out an $|V| \times |V|$ table with for loops and an $O(1)$ sub-problem after running Dijkstra twice (outside the loop), I think I get the following runtime complexity statement:
$$ O(\text{my algorithm}) = O(|V|\mathop{log}|V| + |E|\mathop{log}|V|) + O(|V|^2) $$
Assuming Dijkstra's is implemented with the binary heap.
My problem is that I realized that, worst case, $|E| = |V|^2$, and the statement rewrites as:
$$ O(|V|^2 \mathop{log}|V|) + O(|V|^2) = O(|V|^2\mathop{log}|V|) $$
But, the rest of the time, the algorithm is $O(|V|^2)$, especially if $|E| < |V|$.
What is the correct runtime in this situation? And what is the reasoning behind the correct runtime statement? Because it seems like, to me, just listing out Dijkstra's runtime would be incorrect, since it is only true when the graph is dense... (can I add them together, like: $O(|V|^2 + |E|\mathop{log}|V|)$?)