4
$\begingroup$

(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!)

$\endgroup$
  • $\begingroup$ You mention Dijkstra; have you tried determining the runtime of Dijkstra if you cut after $k$ hops? $\endgroup$ – Raphael Sep 9 '14 at 9:32
  • $\begingroup$ @Raphael Hmm. Its obvious that using Dijkstra is wrong here; simply because it doesn't have the k-hop optimality property after k-iterations. And of course, Dijkstra algorithm's full cycle itself will have less complexity than Bellman-ford, but its useless and that is the point of the question --- To suggest alternative. $\endgroup$ – Loves Probability Sep 9 '14 at 13:44
  • $\begingroup$ I think you are dismissing the idea too quickly. $k$ iterations won't always cover all paths with at most $k$ edges, but that's not the point -- some number of iterations will, and you don't ever have to consider (edge-)longer paths. $\endgroup$ – Raphael Sep 9 '14 at 15:39
  • $\begingroup$ @D.W. and Raphael: Thanks for the comments, hope my edits will clarify your points. $\endgroup$ – Loves Probability Sep 11 '14 at 2:47
  • 1
    $\begingroup$ @D.W. Thanks a lot & I found the problem. I have been doing is a parallel update on all vertices. But the algorithm stated does a sequential update of vertices. Then it cannot be correct. Updating the Question to reflect this issue. $\endgroup$ – Loves Probability Sep 12 '14 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.