<p>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.</p>
<p>For any given <span class="math-container">$n\geq 2$</span>, consider the &quot;star&quot; Directly Acyclic Graph (DAG) of <span class="math-container">$n$</span> vertices and <span class="math-container">$m=n-1$</span> edges, where a central vertex is directly connected to <span class="math-container">$n-1$</span> other vertices, all of which are of degree <span class="math-container">$1$</span>, with distinct weights on their edges (say, from <span class="math-container">$1$</span> to <span class="math-container">$n-1$</span>). Dijkstra's algorithm will run in time within <span class="math-container">$\Theta(m \log n)$</span> on such instance, even though it is a DAG.</p>
<p>A composite algorithm could be checking in linear time (i.e. within <span class="math-container">$O(n+m)$</span> 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 <span class="math-container">$O(m\log n + n+m)\subseteq O(m\log n)$</span> while being faster on DAGs. That would count as an &quot;<a href="https://en.wikipedia.org/wiki/Adaptive_algorithm" rel="nofollow noreferrer">adaptive algorithm</a>&quot; in the broadest sense, if not a very interesting one.</p>
<p>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 &quot;adaptively&quot; in between: I would be interested in reading the description (and analysis) of such an algorithm.</p>

CC BY-SA 4.0
2022-07-09T09:44:59.737Z
2022-07-09T09:44:59.737Z
J.y B.y
<p>I know that Dijkstra's algorithm generally runs in <span class="math-container">$O(E \log V)$</span> using a min-heap. And I know we can use dynamic programming to find the shortest path of a DAG in <span class="math-container">$O(V+E)$</span>. However, I was wondering what happens when we input a DAG into Dijkstra's algorithm? Will it still have a runtime of <span class="math-container">$O(E \log V)$</span> or would it have a faster worst case runtime?</p>
<p>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!</p>

CC BY-SA 4.0
2022-07-07T00:28:24.993Z
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?
Neal Young
<time-complexity><shortest-path>
Does Dijkstra's algorithm run faster on a DAG?
E. Turok
# Does Dijkstra's algorithm run faster on a DAG?

(Asked by: username_0 on 2022-07-06)

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!

**Tags:** time-complexity, shortest-path

> **Comments:**
> **username_1**: 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?  

---

## 1 answers

### Answer by username_2 on 2022-07-09. Score: 0 | Accepted answer

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](https://en.wikipedia.org/wiki/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.


---

