Shortest Path with At Most K Edges

Problem

Find the cheapest path from src to dst that uses at most k edges.

Run k rounds of Bellman-Ford style relaxation, each round reading distances from a frozen copy so every round adds at most one edge. edges is a list of directed [u, v, w] triples. Return -1 if no path within k edges exists, and 0 when src equals dst with k >= 0.

Hint

Copying the distance array each round is what caps the number of edges.

Test cases

case 1

in: [4,[[0,1,1],[1,3,1],[0,2,1],[2,3,5]],0,3,2]

expected: 2

case 2

in: [4,[[0,1,1],[1,3,1],[0,2,1],[2,3,5]],0,3,1]

expected: -1

case 3

in: [3,[[0,1,1],[1,2,1]],0,2,2]

expected: 2

case 4

in: [3,[[0,1,1],[1,2,1]],0,2,1]

expected: -1

case 5

in: [2,[],0,0,0]

expected: 0

Starter codePython

def shortest_path_at_most_k(n, edges, src, dst, k):
    # Your code here
    pass

5 test cases · run your code against them in the editor