Top-K Dependency Paths | Dataford Interview Questions

In a C3 AI pipeline dependency graph, each directed edge (u, v, w) means task u can trigger task v with impact score w. Given a graph, a start node, an end node, and an integer k, return the top k highest-scoring simple paths from start to end, ordered by total score descending.

A path is simple, meaning it cannot visit the same node more than once. The score of a path is the sum of its edge weights.

Formal Specification

Implement a function that takes:

n: number of nodes labeled 0 to n - 1
edges: list of directed edges [from_node, to_node, weight]
start: starting node
end: destination node
k: number of paths to return

Return a list of up to k paths, where each path is represented as [total_score, [node0, node1, ...]].

Constraints

1 <= n <= 15
0 <= len(edges) <= 60
0 <= from_node, to_node < n
-10^4 <= weight <= 10^4
0 <= start, end < n
1 <= k <= 20

Function Signature

def top_k_paths(n, edges, start, end, k):

Your question is Top-K Dependency Paths. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem