Я помогаю другу в проекте, связанном с работой, где ему нужно рассчитать максимальную пропускную способность от узла a до узла b, где пропускная способность у края. Однако максимальная пропускная способность на пути от a до b ограничена ребром с наименьшей пропускной способностью.

Позвольте мне попытаться объяснить с помощью простого примера

Таким образом, граф является ориентированным графом со взвешенными ребрами, и он может быть циклическим. Путь с самой высокой пропускной способностью будет s-> b-> t и будет иметь пропускную способность 250, поскольку этот край устанавливает предел.

Я немного прочитал и обнаружил, что этот тип проблемы"Самая широкая проблема пути" или я бы назвал это чем-то вроде пути с максимальной минимальной емкостью, но я не нашел ни примеров, ни псевдокода, объясняющего, как решить эту проблему.

Я думал о том, чтобы найти все пути от s до t, использовать BFS и каким-то образом только разрешить посещение узла один раз в пути, а затем найти минимальное значение в пути, будет ли это работать?