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

Improve this question
$\endgroup$
13
  • $\begingroup$ You mention Dijkstra; have you tried determining the runtime of Dijkstra if you cut after $k$ hops? $\endgroup$
    – Raphael ♦
    Sep 9, 2014 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, 2014 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, 2014 at 15:39
  • $\begingroup$ @D.W. and Raphael: Thanks for the comments, hope my edits will clarify your points. $\endgroup$
    – Loves Probability
    Sep 11, 2014 at 2:47
  • 2
    $\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, 2014 at 18:30

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.