(Please note, this is not a duplicate to Shortest path with exactly $k$ edges  OR  Shortest path with a fixed number of edges. What I want is a better algorithm)The problem under consideration is to find single-source-shortest-path of at most $k$-edges (simple paths only). What we have is very special case: a Directed Acyclic Graph (DAG) $~G(V,E)~$ with positive edge weights.A preliminary solution to the problem is to run Bellman-Ford to $k$-iterations with parallel relaxation on all edges.Bellman-Ford solution for finding usual shortest-paths, is generally known to be worse in complexity for graphs with positive edge weights. But it is the only algorithm, which possesses the very special property of identifying all $k$-edge optimal paths after $k$-iterations, provided we relax the edges parallelly. This eventually finds all shortest simple paths after at most $|V|-1$ iterations.So simply by stopping the Bellman-Ford algorithm after $k$ iterations, we can find the desired shortest-path of at most $k$-edges from the given source. Also note that, Bellman-Ford algorithm is a classic instance of Dynamic Programming(DP) and the truncated version proposed above is a DP as well.It seems dynamic-programming/Bellman-Ford algorithm (truncated to k-iterations & parallel relaxing of edges) will solve this problem with $O(k|E|)$ complexity. But can we do better at least on a graph with non-negative weights? At least, for a Directed Acyclic Graph(DAG) with non-negative weights!I think it is a legitimate question to ask for a better algorithm, given that we have a much better alternative for usual shortest-path algorithms on graphs with positive weights, namely the Dijkstra's algorithm. Interesting question here is this: Does it extend to finding $k$-edge optimal paths?  This is definitely not immediate, since unlike Bellman-Ford, Dijkstra's doesn't have this property of $k$-edge optimality at $any$ iteration.(Worse thing is that even the constant-factor saving modifications to Bellman-Ford, proposed by Yen, are no more useful for truncated Bellman-Ford.I have a strong hope to have something better!)
Fastest algorithm for shortest path with atmost k edges on a DAG with non-negative edge weights?
algorithms;graphs;search algorithms;shortest path;dag