<p>DAG (Directed acyclic graph) doesn't have to be a connected graph, so the assumption $|E|+2 &gt; |V|$ doesn't hold for some inputs.</p>

CC BY-SA 3.0
2014-02-01T19:35:10.930Z
And if I knew the graph was connected?
Ecir Hana
CC BY-SA 3.0
2014-02-01T19:38:58.247Z
Also, the algorithm uses the weight function to evaluate the cost of an edge. What sense does it make to allow disconnected graph which might not have such function defined for each u, v?
Ecir Hana
CC BY-SA 3.0
2014-02-01T19:46:25.983Z
If you knew that all inputs are connected graphs, the complexity would be indeed $O(|E|)$.
zvisofer
CC BY-SA 3.0
2014-02-01T19:53:55.687Z
For each node $v$ that is not reachable from the source node, the cost of $v$ will remain infinity until the end (all costs were initialized to infinity at the beginning of the algorithm).
zvisofer
CC BY-SA 3.0
2014-02-01T19:19:31.563Z
2014-02-01T19:19:31.563Z
zvisofer
<p>I apologize for seemingly basic question:</p>

<p>I saw numerous times that the time complexity of finding the shortest path in directed acyclic graph is <code>O(|V| + |E|)</code>.</p>

<p>Why there is this <code>|V|</code>? Isn't it always the case that for a connected graph <code>|E|+2 &gt; |V|</code>, hiding the <code>|V|</code> under <code>|E|</code>? I mean:</p>

<pre><code>O(|V| + |E|) =
O(|E| + |E| + 2) =
O(|E| * 2) =
O(|E|)?
</code></pre>

<p>I also think the algorithm for solving the SP only follow the edges, no?</p>

CC BY-SA 3.0
2014-02-01T20:37:36.470Z
[Is $O(n+m)$ really necessary for graph algorithms?](http://cstheory.stackexchange.com/questions/12293/omn-really-necessary-for-graph-algorithms)
Austin Buchanan
CC BY-SA 3.0
2014-02-01T22:37:01.353Z
Please see [about] and [help/on-topic]. This question seems more suitable for [cs.se] which has a broader scope.
Kaveh
CC BY-SA 3.0
2014-02-01T22:38:00.587Z
This website is intended for _research-level questions_ in theoretical computer science, thus this question is off-topic. If you want, I can migrate this question to [CS.SE](http://cs.stackexchange.com/) where there is no research-level restriction.
Artem Kaznatcheev
<graph-theory><graph-algorithms>
Time complexity of finding the shortest path in DAG
Ecir Hana
# Time complexity of finding the shortest path in DAG

(Asked by: username_0 on 2014-02-01)

I apologize for seemingly basic question:
I saw numerous times that the time complexity of finding the shortest path in directed acyclic graph is O(|V| + |E|).
Why there is this |V|? Isn't it always the case that for a connected graph |E|+2 > |V|, hiding the |V| under |E|? I mean:
O(|V| + |E|) =
O(|E| + |E| + 2) =
O(|E| * 2) =
O(|E|)?

I also think the algorithm for solving the SP only follow the edges, no?

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_1**: [Is $O(n+m)$ really necessary for graph algorithms?](http://cstheory.stackexchange.com/questions/12293/omn-really-necessary-for-graph-algorithms)  
> **username_2**: Please see [about] and [help/on-topic]. This question seems more suitable for [cs.se] which has a broader scope.  
> **username_3**: This website is intended for _research-level questions_ in theoretical computer science, thus this question is off-topic. If you want, I can migrate this question to [CS.SE](http://cs.stackexchange.com/) where there is no research-level restriction.  

---

## 1 answers

### Answer by username_4 on 2014-02-01. Score: 0 | Accepted answer

DAG (Directed acyclic graph) doesn't have to be a connected graph, so the assumption $|E|+2 > |V|$ doesn't hold for some inputs.

> **Comments:**
> **username_0**: And if I knew the graph was connected?  
> **username_0**: Also, the algorithm uses the weight function to evaluate the cost of an edge. What sense does it make to allow disconnected graph which might not have such function defined for each u, v?  
> **username_4**: If you knew that all inputs are connected graphs, the complexity would be indeed $O(|E|)$.  
> **username_4**: For each node $v$ that is not reachable from the source node, the cost of $v$ will remain infinity until the end (all costs were initialized to infinity at the beginning of the algorithm).  

---

