0
$\begingroup$

I know that Dijkstra's algorithm generally runs in $O(E \log V)$ using a min-heap. And I know we can use dynamic programming to find the shortest path of a DAG in $O(V+E)$. However, I was wondering what happens when we input a DAG into Dijkstra's algorithm? Will it still have a runtime of $O(E \log V)$ or would it have a faster worst case runtime?

I was thinking that having a DAG would mean that we would only need to relax each vertex once but I'm not sure. Any advice on how to start thinking about this would be appreciated. Thanks!

$\endgroup$
1
  • 2
    $\begingroup$ This seems like a nice homework question. Can you construct a family of DAGs on which Dijkstra's algorithm (implemented with a standard min-heap, in which all operations take $\Omega(\log n)$ time) takes $\Omega(|E|\log|V|)$ time? $\endgroup$
    – Neal Young
    Jul 7, 2022 at 0:28

1 Answer 1

0
$\begingroup$

Relaxing each vertex only once will NOT reduce the worst case complexity of Dijkstra's algorithm among instances where you need to relax each vertex only once.

For any given $n\geq 2$, consider the "star" Directly Acyclic Graph (DAG) of $n$ vertices and $m=n-1$ edges, where a central vertex is directly connected to $n-1$ other vertices, all of which are of degree $1$, with distinct weights on their edges (say, from $1$ to $n-1$). Dijkstra's algorithm will run in time within $\Theta(m \log n)$ on such instance, even though it is a DAG.

A composite algorithm could be checking in linear time (i.e. within $O(n+m)$ if the input is a DAG, output the tree of minimal paths if it's the case, and runs Dijkstra's algorithm otherwise, for a complete running time within $O(m\log n + n+m)\subseteq O(m\log n)$ while being faster on DAGs. That would count as an "adaptive algorithm" in the broadest sense, if not a very interesting one.

An algorithm which complexity grows as the number of edges generating cycles increases would be an interesting algorithms, running in linear time on DAGs, Poly log time on general instances, and "adaptively" in between: I would be interested in reading the description (and analysis) of such an algorithm.

$\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.