Running Time of naive implementation of Dijkstra's Algorithm Here is the &quot;naive&quot; 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 &quot;frontier&quot; between $X$ and $V - X$. Can someone clear up my confusion?
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.