Shortest path from source to destination in directed acyclic graph

Question

There is an approach given in this article Shortest Path in Directed Acyclic Graph to find the shortest path in O(V+E) using topological sort.

I have another approach which I think is more efficient. If use dynamic programming to store the minimum distance from a vertex to a destination than I don't need to explore that node again. Now, time complexity of this solution would be O(V+E) if I am using top to bottom approach (bottom to top approach would be O(V^2).

The advantage of this method is I don't have to find topological order first to find the minimum distance, I can find it directly.

The only disadvantage I can see of this method is, If the depth of my recursion tree is large, then I can run out of stack space and I have to use bottom to top approach. Now, if I have a sparse graph (E=O(V)), time complexity using this method would be O(V^2) but using topological sort method would be O(V) and I can use kahn's algorithm to find topological sort which is done iteratively so running out of stack space wouldn't be an issue.

Is there anything wrong in whatever I have written above?

Answer 1

If your algorithm runs in $O(V+E)$ time, and their algorithm runs in $O(V+E)$ time, I don't see any basis for calling your approach more efficient. At least, asymptotic running time does not seem precise enough to determine which will be more efficient in practice.

Answer 2

No, the time complexity using top to bottom approach would also be $O(V^2)$. So the topological sort method is more efficient as it can find the shortest path in $O(V+E)$.