Single Source Shortest Paths using Product Construction

Question

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?

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.