Чтобы понять пути максимина (часто называемые путями узкого места) в графе, рассмотрим следующую проблему. У вас есть дорожная карта страны в виде графика, где каждый узел представляет пересечение, а каждый край представляет дорогу. У каждой дороги есть ограничение по весу, и если вы едете на грузовике, превышающем ограничение по этой дороге, он сломается. У вас есть грузовик, который вы хотите проехать от начального до конечного пункта, и вы хотите, чтобы на него было максимально возможное количество веса. Учитывая это, по какому пути вы должны вести грузовик, чтобы отправить максимально возможный вес?
Если вы подумаете об этой проблеме, для любого пути, который вы выберете на графике, максимальный вес, который вы можете отправить по этому пути, будет определяться ребром на этом пути с минимальной пропускной способностью. В результате вы хотите найти путь от начала до места назначения, у которого минимальная пропускная способность максимальна. Путь с этим свойством называется путем максимина или узким местом, и его можно найти с помощью простого набора модификаций алгоритмов кратчайшего пути.
Минимаксный путь представляет противоположную идею - путь между двумя точками, который минимизирует максимальную пропускную способность края.
Надеюсь, это поможет!