1
$\begingroup$

I am trying to solve a bounded SSSP problem as follows:

Given a connected weighted graph with non-negative edges (might have cycles), find the shortest path from a vertex s to a vertex t with at most k edges.

I have done some research on this problem. All proposed solutions point to using Bellman-Ford's algorithm by modifying its outer loop to perform k iterations. This will yield a worst case time complexity of O(VE).

I wish to know if it is possible to solve this in O(k * (V+E)LogV) or better using Dijkstra's algorithm?

I have seen this post that discusses the same problem. Dijkstra's algorithm to compute shortest paths using k edges?

However, I don't know how to prove the correctness of the solution that uses product construction.

I have thought of 2 possible (but not necessarily efficient solutions):

1.

Use Breadth first search to mark label the distances of all the nodes within k hops of the source vertex.

Now, if the destination can be reached within k hops, run Dijkstra's algorithm to find the shortest path, using all the labelled nodes, to the destination vertex.

2.

Modify Dijkstra's algorithm such that it will run with a path length counter.

Every time a edge to a vertex is relaxed, mark the distance of that vertex with the counter.

When a vertex is removed from the priority queue:

(a) If the distance value > k, we do not use the vertex

(b) Else we update the counter with the distance value of that vertex.

Now the algorithm should give us the shortest path of max length k.

I am not sure of the correctness and efficiency of my algorithms either. Could someone please advise me if there is a better solution to this problem?

$\endgroup$
  • $\begingroup$ Please rephrase your question so that it's more clear that it is a follow-up question to that other answer. What have you tried and where did you get stuck? Only your last paragraph seems to be new compared to that other question; why is this not a comment on that answer but a full question itself? $\endgroup$ – Raphael Oct 17 '16 at 8:56
  • 1
    $\begingroup$ Note that, as explained in comments over there, Bellman-Ford is more efficient in this setting. $\endgroup$ – Raphael Oct 17 '16 at 8:56
  • $\begingroup$ "All proposed solutions point to using Bellman-Ford's algorithm by modifying its outer loop to perform k iterations. This will yield a worst case time complexity of O(VE)." -- No, it will yield a worst-case time complexity of $O(kE)$, which is better than what you get with Dijkstra. $\endgroup$ – j_random_hacker Oct 17 '16 at 14:12
  • $\begingroup$ @j_random_hacker what if the k is at its maximum? In that case, isn't the complexity O(VE)? Furthermore if |E| is large, then bellman ford will be too slow. $\endgroup$ – LanceHAOH Oct 17 '16 at 23:52
  • $\begingroup$ @LanceHAOH: Yes, but if k=n then the O(k * (V+E)LogV) time complexity you assert for a Dijkstra-based algorithm becomes O(V * (V+E)LogV), which is still strictly worse. Either k is an independent parameter or not, but you have to compare apples with apples! $\endgroup$ – j_random_hacker Oct 18 '16 at 8:13
1
$\begingroup$

The product construction means that you don't just store the shortest distance to a given node, but store the shortest distance to reach a node on a shortest path with $k$ nodes. You certainly don't need to explicitly construct the edges of the product graph. But since the algorithm will produce $k\cdot|V|$ shortest distances of this form, it seems as if you must at least construct an array of this size to hold those distances. However, this is not exactly true, because only the distances different from $\infty$ must be stored.

So you could either generate the nodes of the product graph on the fly and store them in a map (i.e. something like a red black tree), or first determine the reachable part of the product graph by a suitable algorithm. If you only care about the complexity and not about the practical efficiency, then the solution with the map is simpler and still good enough. That map can then also be used for Dijkstra's algorithm itself to determine the next node on which the algorithm continues.

The disadvantage compared to Bellman-Ford's algorithm is that you can't reuse the memory from the previous iteration for the current iteration, because Dijkstra's algorithm will not produce all distance $j-1$ paths before producing distance $j$ paths. But maybe it is possible to modify Dijkstra's algorithm to do exactly this, and this might indeed yield the most efficient algorithm for your problem.

$\endgroup$

Your Answer

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

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