Yen K-Shortest Lite

Problem

Return the costs of the k shortest simple paths from s to t in a small directed weighted graph.

Enumerate all simple paths with DFS from s, collect their costs, sort them, and return the k smallest costs (or fewer when the graph has fewer paths). Return [] when t is unreachable. edges is a list of [u, v, w] triples.

Hint

Yen's algorithm generates deviations from the shortest path instead of enumerating everything.

Test cases

case 1

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

expected: [2,6,7]

case 2

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

expected: [2]

case 3

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

expected: [3,10]

Starter codePython

def yen_k_shortest(n, edges, s, t, k):
    # Your code here
    pass

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