# Does Dijkstra's algorithm run faster on a DAG?

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!

• 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? Jul 7, 2022 at 0:28

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.