# Time complexity of finding the shortest path in DAG [closed]

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?

DAG (Directed acyclic graph) doesn't have to be a connected graph, so the assumption $|E|+2 > |V|$ doesn't hold for some inputs.
• If you knew that all inputs are connected graphs, the complexity would be indeed $O(|E|)$. – zvisofer Feb 1 '14 at 19:46
• 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 Feb 1 '14 at 19:53