2 added 77 characters in body
source | link

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+EV) 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?

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 have to use bottom to top approach. Now, if I have a sparse graph, time complexity using this method would be O(V^2) but using topological sort method would be O(V+E).

Is there anything wrong in whatever I have written above?

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?

1
source | link

Shortest path from source to destination in directed acyclic graph

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 have to use bottom to top approach. Now, if I have a sparse graph, time complexity using this method would be O(V^2) but using topological sort method would be O(V+E).

Is there anything wrong in whatever I have written above?