# Shortest Path problem(Single Source&Destination) [closed]

Given: A completely connected directed acyclic graph.

What would be the most efficient(Least Time complexity) way to find a shortest path among a very large number of nodes?

Constraint:
1)The result should be optimal.
2) The cost between any two connected nodes is computed in time complexity of O(layer-no). For, e.g., if we consider the graph to be layered(Since its a DAG) then the cost between Layer 'K-1' & 'K' can be computed in a time complexity of O(K)

Known Solutions:
1) A* - But heavily dependent on the heuristic function
2) Dynamic programming - requires to compute the cost of path for all possible path.

So, Is there any way to compute it more efficiently or with similar time complexity?

## closed as too broad by D.W.♦, David Richerby, Tom van der Zanden, vonbrand, Kyle JonesJul 12 '15 at 23:36

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• 1. What research have you done? What approaches have you considered? We expect you to do a significant amount of research before asking. See cs.stackexchange.com/help/how-to-ask. 2. What do you mean by "best"? That's ill-defined. 3. The answer is likely to be "it depends" - the answer is likely to depend on the structure of the graph, the information you have, etc. This question probably can't be answered without more context. 4. Asking about how to parallelize is a very different question than how to choose the best serial algorithm. Please pick one to ask about. – D.W. Jul 1 '15 at 1:39
• "Dynamic programming - requires to compute the cost of path for all possible path." -- no, it does not. At each level of the recurrence, all subpaths that are not optimal are thrown away. – Raphael Jul 1 '15 at 10:21

You want the running time to be $O(K)$, where $K$ is the number of layers (or the distance from the source to the destination, I'm not sure which). However, this running time is not achievable. Suppose we have only a handful of layers, but millions of vertices in each layer: say, $K$ layers, but $N/K$ vertices per layer, where $K$ is small and $N$ is large). Then there is no way to get a running time of $O(K)$, because any solution will have to look at every vertex in each of those layers. Therefore, the best you can hope for is a worst-case running time of $O(N)$; $O(K)$ isn't achievable.
The running time of this algorithm is linear, i.e., $O(V+E)$. One can also prove that this is the best worst-case running time one can hope for: it's not possible to do any better, in terms of asymptotic worst-case running time. So, from a theoretical perspective, the standard algorithm is excellent.