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.

Could someone please advise me?

  • $\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, 2016 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, 2016 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$ Oct 17, 2016 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$
    – Donald
    Oct 17, 2016 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$ Oct 18, 2016 at 8:13

1 Answer 1


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.


Your Answer

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

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