1
$\begingroup$

I was able to understand the problem of at most k edges and exactly k edges but I am not able to wrap my head around how do I solve the problem of getting shortest paths with at least k edges. You can traverse same edge twice until you reach the minimum required number of edges. An example of implementation is going from one place to another but in between you want to get frequent flyer status and for that you must travel at least k places

Below are few web pages I followed

https://leetcode.com/problems/cheapest-flights-within-k-stops/discuss/686939/Python-by-DP-with-Bellman-Ford-algorithm-w-Comment https://courses.cs.washington.edu/courses/cse421/06au/slides/Lecture21/Summary21.html http://web.stanford.edu/class/archive/cs/cs161/cs161.1176/Slides/Lecture12-lowquality.pdf

$\endgroup$

1 Answer 1

1
$\begingroup$

Use a product construction: make $k$ copies of the graph, where each edge goes from the $i$th copy to the $i+1$th copy (and also edges from the $k$th copy to itself), then compute shortest paths in this graph. I'll let you fill in the details.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.