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

  1. [20 минут] Невзвешенный граф
    1. [15 минут] bfs (алгоритм без очереди, алгоритм с очередью, восстановление пути и сравнение с dfs, граф кратчайших путей, куда идут рёбра, код!)
    2. [5 минут] матрица расстояний за O(VE)
    3. [в практику] матрица расстояний за O(V3/w)
  2. [15 минут] Модификации bfs для взвешенного графа
    1. Форд-Беллман с очередью как аналог bfs (позже докажем, что он за O(VE) работает)
    2. 1-k-bfs: (1 ребро → k рёбер) и (k+1 очередь)
    3. 0-1-bfs: (очередь → дек)
    4. [в практику] k-2k-bfs, 1-2-bfs (вещественные), 0-1-bfs (вещественные)
  3. [25 минут] Дейкстра
    1. Дейкстра за V*ExtractMin + E*DecreaseKey (V2, ElogV)
    2. [в практику] Дейкстра за E + VlogV, ElogE/V+1V, EloglogC
    3. Алгоритм A*
  4. [10 минут] Классификация задач поиска пути
    1. Невзвешенный граф: bfs, O(E), 1950.
    2. Граф без отрицательных рёбер: Дейкстра за O(n2), O(mlogn), O(m + nlogn), O(m + nlogC), O(m + nsqrtlogC)
    3. На самом деле еще умеют для неорграфов искать путь за O(n + m), и для орграфов за O(m + nloglogmin(n,C))
    4. [практика] Отрицательные рёбра, отрицательные циклы, алгоритма для минимального простого пути не существует
    5. Граф с отрицательными весами рёбер: 58' Ford,Bellman − O(EV), 93' Goldberg − O(EV1/2logN)
  5. [15 минут] Алгоритм Флойда
    1. Пишем 3 цикла (проверять ли бесконечность)
    2. Доказываем корректность подсчёта расстояния (динамика)
    3. Восстанавливаем путь (доказательство того, что если нет отрицательных циклов: не циклится, путь простой)
    4. Восстанавливаем отрицательный цикл (без док-ва, объяснить, почему)
    5. Транзитивное замыкание за O(V3/w)