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):1.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.2.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?
Single-Source Shortest Path with at most k edges using Dijkstra's algorithm
algorithms;graphs;optimization;shortest path