# Single Source Shortest Paths using Product Construction

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.

• 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?
– Raphael
Oct 17 '16 at 8:56
• Note that, as explained in comments over there, Bellman-Ford is more efficient in this setting.
– Raphael
Oct 17 '16 at 8:56
• "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. Oct 17 '16 at 14:12
• @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. Oct 17 '16 at 23:52
• @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! Oct 18 '16 at 8:13

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.
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.