Running Time of naive implementation of Dijkstra's Algorithm

Question

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?

Answer 1

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.