1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Your question is very hard to read. Perhaps you could fix the typesetting. $\endgroup$ – Yuval Filmus Dec 23 '16 at 6:32
  • $\begingroup$ Sorry about this. Can you tell me which parts specifically should be fixed? $\endgroup$ – FrostyStraw Dec 23 '16 at 6:33
  • $\begingroup$ Some examples are = / = and various stars. The code could also be typeset better. $\endgroup$ – Yuval Filmus Dec 23 '16 at 6:35
  • $\begingroup$ 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 *) $\endgroup$ – FrostyStraw Dec 23 '16 at 6:38
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.