Widest Path Maximum Capacity

Problem

Find the path from src to dst that maximizes the minimum edge capacity along the path (the widest path).

Use a max-heap search where each node keeps the best bottleneck value found so far. edges is a list of directed [u, v, capacity] triples. Return the widest bottleneck, or -1 when dst is unreachable; if src equals dst return 0.

Hint

A widest path problem is a shortest path problem on negated capacities.

Test cases

case 1

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

expected: 4

case 2

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

expected: -1

case 3

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

expected: 4

case 4

in: [2,[],1,1]

expected: 0

Starter codePython

import heapq
def widest_path(n, edges, src, dst):
    # Your code here
    pass

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