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
|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?