# 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. – Yuval Filmus Dec 23 '16 at 6:32
• Sorry about this. Can you tell me which parts specifically should be fixed? – FrostyStraw Dec 23 '16 at 6:33
• Some examples are = / = and various stars. The code could also be typeset better. – Yuval Filmus Dec 23 '16 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 *) – FrostyStraw Dec 23 '16 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.