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?