1
$\begingroup$

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?

$\endgroup$

closed as too broad by D.W., David Richerby, Tom van der Zanden, vonbrand, Kyle Jones Jul 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.

  • 3
    $\begingroup$ 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. $\endgroup$ – D.W. Jul 1 '15 at 1:39
  • 1
    $\begingroup$ "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. $\endgroup$ – Raphael Jul 1 '15 at 10:21
3
$\begingroup$

Your goals are not achievable.

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.

So, there is no algorithm that will meet your constraints.


That's the bad news. The good news is that there is an algorithm that is efficient and has a running time that is asymptotically optimal. This is the standard algorithm for computing shortest paths in a DAG: you topologically sort the DAG, then visit the vertices in topologically sorted order, calling "Relax" on each edge. Any good algorithms textbook is likely to describe this algorithm.

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.

Now this doesn't rule out the possibility that clever implementation can improve the constant factors. Indeed, it is likely that careful consideration of things like the structure of your graphs and the memory hierarchy might yield speedups that are measurable in practice. But you shouldn't expect an improvement in the asymptotic running time.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.