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):
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.
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?