# Running Time of naive implementation of Dijkstra's Algorithm

Here is the "naive" implementation of Dijkstra's algorithm that the professor uses:

For a directed graph $$G = (V,E)$$ as input

Initialize:

• $$X = \{s\}$$ (the vertices processed so far)

• $$A[s] = 0$$ (computed shortest path distance)

• $$B[s] = empty path$$ (computed shortest path)

Main Loop:

While $$X \neq V$$:

• Among all edges $$(v,w) ∈ E$$ with $$v ∈ X$$, $$w \notin X$$, pick the one that minimizes $$A[v] + \ell_{vw}$$, where $$\ell_{vw}$$ is the length of the edge between $$v$$ and $$w$$. Call this edge $$(v^*,w^*)$$ .

• Add $$w^*$$ to $$X$$.

• Set $$A[w^*] = A[v^*] + \ell_{u^*w^*}$$.

• Set $$B[w^*] = B[v^*] \cup \{(v^*w^*)\}$$.

The running time for this is given as $$O(nm)$$, where $$n = |V|$$ and $$m = |E|$$. I don't fully understand why. He says $$n$$ is the number of loop iterations, which I understand, but that $$m$$ is the work per iteration (a linear scan through edges to compute the minimum). But if it's doing $$m$$ work per iteration, that would imply that it's looking at every single edge in the graph, when it should only be looking at edges that cross the "frontier" between $$X$$ and $$V - X$$. Can someone clear up my confusion?

• Your question is very hard to read. Perhaps you could fix the typesetting. Dec 23, 2016 at 6:32
• Sorry about this. Can you tell me which parts specifically should be fixed? Dec 23, 2016 at 6:33
• Some examples are = / = and various stars. The code could also be typeset better. Dec 23, 2016 at 6:35
• The =/= was trying to say "not equal to" but I wasn't sure how to write it better. The stars are just because the lecturer decided to call the minimum edge chosen (v * w *) Dec 23, 2016 at 6:38

In each iteration we need to go over all edges crossing the cut $(X,V\setminus X)$. The algorithm doesn't explain how we do that, so it is difficult to analyze the exact running time, though $O(m)$ per iteration is definitely an upper bound. A naive implementation will presumably go over all edges, checking which of them cross the cut, and for this implementation, the running time will indeed be $\Theta(m)$ per iteration.