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?