Editorial for Bottleneck Paths

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

The graph is undirected and connected with $n \le 100$ ~n \le 100~, so an $O(n^3)$ ~O(n^3)~ all-pairs algorithm is acceptable.

This is the same shape as Floyd–Warshall, except the path cost is the maximum edge weight on the path, and we want to minimize that cost. Initialize a dense matrix with direct edge weights (taking the minimum on parallel edges), zeros on the diagonal, and $\infty$ ~\infty~ elsewhere. Then, for each intermediate vertex $k$ ~k~ and every pair $(i, j)$ ~(i, j)~, relax

$best[i][j] = \min\bigl(best[i][j],\ \max(best[i][k], best[k][j])\bigr)$ .

After every $k$ ~k~ is processed, $best[i][j]$ ~best[i][j]~ is the minimum achievable bottleneck between $i$ ~i~ and $j$ ~j~.

The time complexity is $O(n^3)$ ~O(n^3)~.

Solution (Python)

import sys

INF = 10**18


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, m = data[0], data[1]
    best = [[INF] * n for _ in range(n)]
    for i in range(n):
        best[i][i] = 0

    idx = 2
    for _ in range(m):
        u = data[idx] - 1
        v = data[idx + 1] - 1
        w = data[idx + 2]
        idx += 3
        if w < best[u][v]:
            best[u][v] = w
            best[v][u] = w

    for k in range(n):
        bk = best[k]
        for i in range(n):
            bik = best[i][k]
            if bik == INF:
                continue
            bi = best[i]
            for j in range(n):
                bkj = bk[j]
                if bkj == INF:
                    continue
                cand = bik if bik >= bkj else bkj
                if cand < bi[j]:
                    bi[j] = cand

    out_lines = [" ".join(map(str, row)) for row in best]
    sys.stdout.write("\n".join(out_lines) + "\n")


if __name__ == "__main__":
    main()

Comments

There are no comments at the moment.