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) =

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


closed as off-topic by Hsien-Chih Chang 張顯之, Marzio De Biasi, András Salamon, Jeffε, Kaveh Feb 4 '14 at 23:32

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Hsien-Chih Chang 張顯之, Marzio De Biasi, András Salamon, Jeffε, Kaveh
If this question can be reworded to fit the rules in the help center, please edit the question.


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

  • $\begingroup$ And if I knew the graph was connected? $\endgroup$ – Ecir Hana Feb 1 '14 at 19:35
  • $\begingroup$ 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? $\endgroup$ – Ecir Hana Feb 1 '14 at 19:38
  • $\begingroup$ If you knew that all inputs are connected graphs, the complexity would be indeed $O(|E|)$. $\endgroup$ – zvisofer Feb 1 '14 at 19:46
  • $\begingroup$ 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). $\endgroup$ – zvisofer Feb 1 '14 at 19:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.