Тот же алгоритм с другими операциями

Если ты умеешь получать транзитивное замыкание и путь максимальной пропускной способности из того же кода и знаешь, когда брать Флойда, а когда V Дейкстр, листай до «Теперь сам».

Как думаешь, что ещё считается этими циклами

Формула Флойда говорит: «лучший путь из i в j через вершины до k - это либо старый путь, либо склейка двух кусков через k». Прежде чем читать дальше, ответь: где в этой фразе спрятана операция «сложить длины», а где - «выбрать лучший»? И что получится, если заменить их на другие?

На что это похоже

Один и тот же маршрутный лист, по которому считают разное. Сложив длины участков, получаем километраж. Взяв минимум по ширине мостов, получаем, какой груз пройдёт по маршруту. Взяв произведение вероятностей «участок исправен», получаем надёжность. Маршрут один, арифметика разная - и каждая арифметика отвечает на свой вопрос.

Механизм: одна схема, разные операции

Что такое полукольцо. Так называют пару операций «склеить» и «выбрать лучшее», от которой требуется три вещи. Первая: склейка АССОЦИАТИВНА - склеить первые два куска пути, а потом третий, то же самое, что склеить второй с третьим, а потом приставить первый; иначе «длина пути» зависела бы от того, как его делить. Вторая: у склейки есть нейтральный элемент - значение, склейка с которым ничего не меняет (для + это 0, для × единица, для min - +∞); именно оно и стоит на диагонали. Третья: склейка распределяется над выбором лучшего, то есть «лучшее из склеенных» равно «склейке лучших» - на этом и держится формула, ведь она склеивает два УЖЕ выбранных лучших куска. Проверить свою пару просто: возьми три числа и убедись, что скобки не важны, а потом проверь распределение на двух вариантах. У (min, +), (max, min), (min, max), (max, ×) и (ИЛИ, И) всё это есть; у «вычесть вдоль пути» ассоциативности нет, и шаблон рассыпается.

общая форма:   d[i][j] = ЛУЧШЕЕ( d[i][j],  СКЛЕИТЬ( d[i][k], d[k][j] ) )

задача                      ЛУЧШЕЕ   СКЛЕИТЬ   диагональ   нет ребра
кратчайший путь             min      +         0           +∞
достижимость (Уоршелл)      ИЛИ      И         истина      ложь
максимальная пропускная     max      min       +∞          0
минимаксный путь            min      max       0           +∞
самый надёжный путь         max      ×         1           0

Две правые колонки легко перепутать, а путать их нельзя. На ДИАГОНАЛИ стоит нейтральный элемент склейки: «никуда не идти» не должно портить путь, а d[i][i] участвует в формуле как обычная клетка. Там, где РЕБРА НЕТ, стоит худшее возможное значение - такое, которое «ЛУЧШЕЕ» никогда не выберет. Для кратчайших путей это 0 и +∞; для пропускной способности - наоборот, +∞ и 0: проехать «сам в себя» можно с любым грузом, а по отсутствующей дороге - ни с каким.

Транзитивное замыкание целиком:

for k in range(V):
    for i in range(V):
        for j in range(V):
            reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])

Практический приём: хранить строку reach[i] не списком из V истин и лжей, а ОДНИМ целым числом, у которого j-й бит означает «из i достижима j» - на 64 вершины уходит одно машинное слово, которое процессор обрабатывает целиком за одну операцию. Тогда внутренний цикл по j исчезает: вместо V проверок пишется одна строка reach[i] |= reach[k] (знак |= - это «поразрядное ИЛИ и присвоить», то же, что reach[i] = reach[i] | reach[k]: в результате бит стоит там, где он стоял хотя бы в одном из двух чисел). Выполняется она при условии reach[i][k], то есть когда из i вообще можно добраться до k. Асимптотика остаётся O(V³), но делится на размер слова: на 64-битных словах это ускорение примерно в 64 раза, то есть разница между «минута» и «час». Дальше в уроке я называю это «в десятки раз» - имеется в виду ровно этот множитель.

Выбор алгоритма для всех пар:

плотный граф, небольшое V        → Флойд-Уоршелл, O(V³), код в пять строк
разреженный, неотрицательные веса → V Дейкстр, O(V·E·log V)
разреженный, есть отрицательные   → Джонсон (потенциалы + V Дейкстр)
нужна только достижимость         → Уоршелл на битовых словах

Правило

Тройка циклов Флойда работает для любой пары операций «склеить вдоль пути» и «выбрать лучший путь»: (min, +) - кратчайшие пути, (ИЛИ, И) - транзитивное замыкание (Уоршелл), (max, min) - максимальная пропускная способность, (min, max) - минимаксный путь, (max, ×) - самый надёжный путь. Диагональ инициализируется нейтральным элементом склейки. Транзитивное замыкание на битовых словах ускоряется в десятки раз (на 64 вершины - одно слово) при той же асимптотике. Выбор между Флойдом, V Дейкстрами и Джонсоном - по плотности графа и знаку весов.

Разбор: транзитивное замыкание по шагам

Граф: 0→1, 1→2, 2→3. Матрица достижимости в начале - это просто рёбра (плюс диагональ):

        0  1  2  3
    0 [ 1  1  0  0 ]
    1 [ 0  1  1  0 ]
    2 [ 0  0  1  1 ]
    3 [ 0  0  0  1 ]

k = 0: ничего не меняется - в ноль никто не входит
k = 1: reach[0][2] = reach[0][1] И reach[1][2] = 1 → появилось
k = 2: reach[0][3] = reach[0][2] И reach[2][3] = 1 → появилось
       reach[1][3] = reach[1][2] И reach[2][3] = 1 → появилось
k = 3: ничего - из тройки рёбер нет

итог: из 0 достижимы 1, 2, 3; из 1 - 2 и 3; из 2 - 3

Заметь, что порядок k снаружи важен здесь ровно так же: на шаге k = 2 мы пользуемся значением reach[0][2], которое появилось только на предыдущем шаге. Если бы k был внутренним циклом, цепочка достижимости «через две пересадки» могла бы не собраться.

Разбор: путь с максимальной пропускной способностью

Задача: по маршруту везут груз, у каждой дороги свой предел по весу. Пропускная способность МАРШРУТА - это минимум по его дорогам («узкое место»), а нам нужен маршрут, у которого это узкое место максимально.

Формула: cap[i][j] = max( cap[i][j], min(cap[i][k], cap[k][j]) ).

дороги: 0→1 предел 7, 1→2 предел 5, 0→2 предел 4

k = 1:  min(cap[0][1], cap[1][2]) = min(7, 5) = 5
        max(4, 5) = 5  →  cap[0][2] = 5

Ответ: 5 - вези через город 1, там узкое место шире. Прямая дорога выдерживает только 4, хотя она и короче в рёбрах. Обрати внимание, что «длина» здесь ни при чём: задача другая, а алгоритм тот же.

Тот же приём используют в сетях (максимальная пропускная способность маршрута), в задачах про надёжность (там склейка - умножение вероятностей, а лучший - максимум) и в геометрии (минимаксные пути: минимизировать самый тяжёлый участок).

Что ломается без этого

Первое: менять операции, но забыть про нейтральный элемент на диагонали: для (max, min) это +∞, для (max, ×) - единица, для достижимости - истина; ноль там всё сломает. Второе: применять шаблон к паре операций, которая не образует полукольца (например, «вычесть вдоль пути») - результат будет бессмысленным, потому что склейка перестанет быть ассоциативной. Третье: считать, что битовое ускорение меняет асимптотику - нет, оно делит константу на размер слова. Четвёртое: брать Флойда для «все пары» на разреженном графе с тысячами вершин: 10⁹ операций там, где V Дейкстр справятся за минуты. Пятое: считать надёжность сложением вместо умножения - вероятности вдоль пути перемножаются. Если хочется вернуться к привычному (min, +), берут −log p: логарифм превращает произведение в сумму, а минус переворачивает сравнение - самая надёжная цепочка (максимум произведения) становится самой короткой (минимум суммы). Вероятности не больше единицы, поэтому −log p >= 0, и такие веса годятся даже Дейкстре.

Зачем это в работе

Транзитивное замыкание нужно в анализе зависимостей («какие модули потянет за собой изменение этого»), в базах данных (рекурсивные запросы «все подчинённые»), в статическом анализе кода (достижимость по графу вызовов), в проверке прав доступа по иерархии ролей. Пропускная способность маршрута - в сетях и логистике. Но главное, что стоит унести, - сама привычка видеть в алгоритме ШАБЛОН, а не рецепт: если структура вычисления «лучшее по всем склейкам» совпадает, менять можно только операции. Это сильно экономит: вместо десяти алгоритмов в голове остаётся один плюс таблица операций.

Теперь сам

Граф дорог: a→b предел 3, b→c предел 6, a→c предел 2, c→d предел 4. Найди маршрут из a в d с максимальной пропускной способностью. Какие операции ты при этом подставил в шаблон?