Кратчайшие пути в графах (12 февраля 2021)

  1. Дерево игры (остаток с прошлой лекции)
    1. Игра на 0-1 дереве. O(1.7n)
    2. AND-OR дерево
    3. minimax. Бинпоиск+
    4. minimax. αβ-отсечение

  2. [2 минут] Классификация и определение задач: SSSP, APSP, орграф
  3. [20 минут] Невзвешенный граф
    1. [5 минут] bfs алгоритм без очереди (Ad − вершины до которых расстояние ровно d)
    2. [5 минут] bfs с очередью q = A0 + A1 + A2 + ...
    3. [5 минут] восстановление пути, сравнение с dfs, ацикличный граф кратчайших путей (вдруг нам нужно несколько кратчайших путей?)
    4. APSP: матрица расстояний за O(VE)
    5. [skipped] [в практику] матрица расстояний за O(V3/w)

  4. [15 минут] 1-k и 0-k BFS (модификации bfs для взвешенного графа)
    1. 1 ребро → k рёбер: Что делать если веса 1..k? Раскатерим! O(k(V+E))
    2. 1-k-bfs: VK+1 очередь, k+1 очередь (время работы: внешний цикл за VK, рёбра за E)
    3. 0-k-bfs: то же, но можем "класть в себя"
    4. 0-1-bfs: берём bfs c 1 очередью, заменяем очередь на дек. Корректность следует из изоморфности 0-k-bfs-у для k=1 (дек = 2 очереди).
    5. [skipped] [в практику] k-2k-bfs, 1-2-bfs (вещественные), 0-1-bfs (вещественные)

  5. [10 минут] Дейкстра
    1. Алгоритм. Корректность: у вынутой вершины оптимально расстояние (от противного).
    2. Оценка времени V*ExtractMin + E*DecreaseKey (V2, ElogV)
    3. [skipped] [в практику и дз] Дейкстра за E + VlogV, ElogE/V+1V, EloglogC
    4. Дейкстра и отрицательные веса: в принципе работает если много раз вынимать одну и ту же вершину из кучи. На практике покажем, что экспоненту.
    5. Задача про города на плоскости. Двусторонняя Дейкстра (картинка с двумя кругами). Описание алгоритма A* (оценка пути снизу).
− Перерыв −
  1. [15 минут] Алгоритм A*
    1. Алгоритм: d[v] → d[v]+f[v] (природа f − оценка длины пути снизу)
    2. Корректность и время работы
      1. Lm о неравенстве треугольника: вытащим каждую вершину ≤ 1 раза
      2. (нер-во треугольника) + (f[v] ≥ 0) + (f[t] = 0) ⇒ переберём подмножество вершин Дейкстры.
    3. Иллюстрация "существует почти прямой путь".

  2. [10 минут] Что вообще бывает для SSSP?
    1. SSSP: Невзвешенный граф: bfs, O(E), 1950.
    2. SSSP: Граф без отрицательных рёбер: Дейкстра за O(n2), O(mlogn), O(m + nlogn), O(m + nlogC), O(m + nsqrt(logC))
    3. SSSP: На самом деле еще умеют для неорграфов искать путь за O(n + m), и для орграфов за O(m + nloglogmin(n,C))
    4. SSSP: Граф с отрицательными весами рёбер: 58' Ford,Bellman − O(EV), 93' Goldberg − O(EV1/2logN)
    5. [skipped] [ушло в практику] SSSP. Отрицательные рёбра, отрицательные циклы, алгоритма для минимального простого пути не существует

  3. [15 минут] Алгоритм Флойда
    1. Пишем 3 цикла
    2. Доказываем корректность подсчёта расстояния (следует из динамики)
    3. Восстанавливаем путь двумя способами next[a,b] и middle[a,b] (доказательство того, что если нет отрицательных циклов: не циклится, путь простой)
    4. Lm: отрицательный цикл через i ⇔ d[i][i] < 0
    5. Восстанавливаем отрицательный цикл (без док-ва, но объяснить интуицию, почему работает)
    6. [skipped] [ушло в практику] Транзитивное замыкание за O(V3/w)

  4. Дополнительные главы
    1. Извлечение корня по модулю за logn
    2. Перебор с отсечением по ответу (по типу A*)
    3. beam-search и применения