Max Throughput DAG Path | Dataford Interview Questions

Write an algorithm to find the maximum throughput path in a directed acyclic graph representing a distributed computational pipeline.

Given n, weighted directed edges [u, v, throughput], a source, and a sink, return [maximum_throughput, path], where a path's throughput is the minimum edge throughput along it. Return [-1, []] if the sink is unreachable.

Example: n=4, edges=[[0,1,8],[0,2,5],[1,3,4],[2,3,5]] returns [5, [0,2,3]]. Equal-throughput paths may return any valid path.

Constraints: 1 <= n <= 5000, the graph is acyclic, throughput values are positive integers, and source != sink.

Constraints

1 <= n <= 5000
0 <= len(edges) <= 20000
Each edge is [u, v, throughput]
0 <= u, v < n
1 <= throughput <= 10^9
The graph is directed and acyclic
source != sink

Function Signature

def maximum_throughput_path(n, edges, source, sink):

Your question is Max Throughput DAG Path. 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