Кратчайшие пути в графах (5 марта 2018)

  1. [25 минут] Алгоритм Форда-Беллмана
    1. Реализация за O(VE) c двумерным массивом, доказательство корректности
    2. Реализация за O(VE) c одномерным массивом
    3. Реализация за O(kE) (c break)
    4. Реализация с очередью, работающая в худшем случае за O(VE), и за O(E) в среднем
    5. Реализация с random shuffle
    6. [Практика] Попытка написать Дейкстру для графов с отрицательными весами.
    7. [skipped] Алгоритмы с добавлением в начало, Левита.

  2. [15 минут] Поиск цикла отрицательного веса Форд-Беллманом
    1. Алгоритм за O(VE), проверяющий наличие
    2. Восстановление цикла за O(V)
    3. Доказательство корректности восстановления (3 леммы)
    4. [skipped] Использование идеи "Форд-Беллмана с очередью" для поиска за O(E) в среднем
− Перерыв −
  1. [10 минут] Потенциалы Джонсона
    1. Определение потенциалов, сохранение кратчайшести, неотрицательные веса
    2. Поиск потенциалов = Форд-Беллман, алгоритм Джонсона решения APSP

  2. [skipped] [т.к. дедлайны по ДЗ] [5 минут] Итоги
    1. 1-k-bfs: 0-1-R и A-B-R для A > 0.
    2. APSP: Джонсон
    3. SSSP: Форд-Белман, Дейкстра, 1-k-bfs
    4. Из не пройденного: Гольдберг, разные крутые кучи для Дейкстры, Торуп

  3. [30 минут] Поиск цикла минимального среднего веса.
    1. [5 минут] Алгоритм бинпоиском.
    2. [5 минут] Оценка точности бинпоиска 1/n2
    3. [5 минут] Алгоритм Карпа за O(VE): μ = minv maxk (d[n,v] - d[k,v]) / (n - k);
    4. [15 минут] Доказательство алгоритма Карпа
      1. Вычтем из всех рёбер x, μ уменьшится ровно на x
      2. Доказываем того что μ = 0 для случая ans = 0: знаменатель сразу уходит, нужно доказать (а) d[n,v] ≥ mink, (б) ∃v : d[n,v] = mink
− Перерыв −
  1. [45 минут] Алгоритм Гольдберга (по желанию)
    1. Анонс: делаем алгоритм за O(EV1/2logN) для целых весов, сперва научимся за O(EV1/2) делать для весов [-1..∞)
    2. Суть − найти правильные потенциалы, будем по чуть-чуть избавляться от отрицательных рёбер. Сперва за O(VE).
    3. Берём вершину v, в которую есть входящее ребро -1, меняем ей потенциал на -1.... Входящим рёбрам ок, а исходящим? Придётся взять всю компоненту, достижимую из v по 0 и -1 рёбрам.
    4. Как ускорить? Одним махом за O(E) лечить не одну вершину, а пачку O(k1/2) вершин, где k − число вершин с отрицательными рёбрами.
    5. Сжали компоненты сильной связности по 0 и -1, в конденсации запустили динамику, считающую расстояние от фиктивной вершины s в графе с -1 и 0 рёбрами.
    6. Или есть путь длины -k1/2 (а на нём хотя бы k1/2 интересных вершин), или есть слой (вершины на одинаковом расстоянии) из k1/2 вершин
    7. Слой: очевидно
    8. Путь: с конца в начало идём и делаем S1, S2, ... St добавление -1 к потенциалу. (Si − посещённые на i-м шаге вершины, Si ⊂ Si+1)
    9. Скорость сходимости (сколько раз нужно из числа вычесть его корень?)
    10. Добавим logN: сейчас рёбра делятся на 3 группы = {-1, 0, >0}, для -(2k+1) будут делиться на {-(2k+1)..-(k+1), -k..0, >0}