Analysis of Dijkstra algorithm's (Lazy) running time

Question

I'm trying to figure out the running time for a Dijkstra algorithm. All the sources I have read say that the running time is O(E * log (E)) for a lazy implementation.

But when we do the math we get O(E * (Log(E)+E*Log(E))).

Since E isn't a constant, I don't see how someone could reduce this to O(E * log (E).

Are we analyzing the wrong or is it possible to reduce?

        while (!minPQ.isEmpty()) { <=== O(E)
            Node min = minPQ.poll(); <=== O(log(e)

            for (Edge edge : graph.adj(min)) { <=== O(E)
                if (min.getId() == target.getId()) {
                    // Source and Target = Same edge
                    if (edgeTo.size() == 0) edgeTo.put(target, edge);

                    return;
                }

                relax(edge, min, vehicle); <=== log(e) (because of add method on PQ)
            }
      }

Answer 1

First of, you can make some of the bounds a little tighter and replace some $E$s with $V$s. The while loop at the beginning will only run $O(|V|)$ iterations (you visit every node only once), and the for (Edge edge : graph.adj(min)) loop will run only $O(|V|)$ iterations at most (a node can have at most $O(|V|)$ adjacent edges). Same with the log factors, although in that case it doesn't matter as much since $O(\log |V|) = O(\log |E|)$ (if the graph is connected). Via simple multiplication this gives you $O(|V| \cdot (\log |V| + |V| \cdot \log |V|)) = O(|V|^2 \cdot \log |V|)$. In a dense graph, this is already the desired complexity. Since a dense graph has $O(|V|^2) = O(|E|)$.

However in a sparse graph, e.g. when $O(|E|) = O(|V|)$, then you can still do a lot better.

The problem you are facing is that multiplying the upper bounds can lead to overestimation. Look at the following example:

for (i = 1 to N) {
    limit = N if i == 1 else 1
    for (j = 1 to N) {
        constant_work()
    }
}

The outer loop clearly runs $O(N)$ times, and the inner loop runs also $O(N)$ times (because in the worst case it does). You can say that in total the complexity is $O(N^2)$ times. But this is just an upper bound.

Most of the time the inner function actually does almost no work. In reality if you count the number of times you run the function constant_work(), you will get $$N + 1 + 1 + \cdots + 1 = 2N - 1 = O(N)$$ $N$ iterations for i == 1 and otherwise only $1$ iteration. So the code runs in $O(N)$ time.

The same effect happens when you loop over edges next to a node: for (Edge edge : graph.adj(min)). Yes, in the worst case you have $O(|V|)$ edges, but in a sparse graph, most of the time you have a lot less.

You can count them from a different angle. If you fixate an edge $(u, v)$, how often will you touch that edge, and move into the body of the loop? Only twice! Once when min == u, and once when min == v. Therefore the inner part of the loop, with runtime $O(\log |V|)$, will run only $O(2 |E|) = O(|E|)$ times. Which means that the whole thing runs in $O(|E| \log |V|)$.

Answer 2

Your analysis is correct, but not tight.

Instead of considering the while loop and the for loop separately, it is better to consider them together. The inner body of the for loop runs once for each (vertex,pair) edge, for a total of $2|E|$ times. Therefore the total running time of all relax operations is only $O(|E|\log |E|$).

The total running time of all poll operations is also $O(|E|\log |E|)$, as you also observe, and we deduce that the total running time is $O(|E|\log |E|)$.