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?


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

| cite | improve this answer | |
  • $\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.