Как найти кратчайший путь, минимизирующий максимальное ребро (minimax-путь)?
Нестандартная задача: нужен путь из s в t, у которого самое тяжёлое ребро минимально (а не сумма). Например, проехать так, чтобы максимальная высота на маршруте была как можно меньше. Дейкстра минимизирует сумму — как переделать под максимум?
2 ответа
Это minimax-путь (минимаксный, bottleneck). Берём Дейкстру, но меняем операцию релаксации: вместо суммы dist[v] + w используем max(dist[v], w) — стоимость пути = максимальное ребро на нём.
vector<ll> dist(n, INF);
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
dist[s] = 0; pq.push({0, s});
while (!pq.empty()) {
auto [d, v] = pq.top(); pq.pop();
if (d > dist[v]) continue;
for (auto [u, w] : g[v]) {
ll nd = max(d, (ll)w); // не сумма, а максимум ребра
if (nd < dist[u]) { dist[u] = nd; pq.push({nd, u}); }
}
}
Сложность O(E log V) — та же Дейкстра. Корректность сохраняется, потому что max так же монотонен, как сумма: добавление ребра не уменьшает значение пути.
Альтернатива — через минимальное остовное дерево: минимаксный путь между любыми двумя вершинами идёт по рёбрам MST (свойство bottleneck spanning tree). Если нужны minimax-расстояния между всеми парами — строим MST (Краскал) и отвечаем на запросы через LCA/бинарные подъёмы по дереву, максимум ребра на пути. Это эффективнее, чем V раз запускать модифицированную Дейкстру, когда запросов много. Зеркальная задача (maximin — максимизировать минимальное ребро, «самый широкий путь») решается так же, поменяв min/max местами.