Bottleneck Path Min Max Edge

Problem

Find the path from src to dst that minimizes the maximum edge weight along the path (the minimax or bottleneck path).

Use a Dijkstra-like search where the cost of a node is the smallest possible maximum edge on a path to it. Return that cost, or -1 when dst is unreachable, and 0 when src equals dst. edges is a list of [u, v, w] triples for an undirected graph.

Hint

The optimal bottleneck path always lies inside the MST path between the endpoints.

Test cases

case 1

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

expected: 4

case 2

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

expected: 2

case 3

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

expected: -1

case 4

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

expected: 0

case 5

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

expected: 2

Starter codePython

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

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