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

1. [20 минут] Невзвешенный граф
1. [15 минут] bfs (алгоритм без очереди, алгоритм с очередью, восстановление пути и сравнение с dfs, граф кратчайших путей, куда идут рёбра, код!)
2. [5 минут] матрица расстояний за O(VE)
3. [в практику] матрица расстояний за O(V³/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. [10 минут] Дейкстра
1. Дейкстра за V*ExtractMin + E*DecreaseKey (V², ElogV)
2. [в практику] Дейкстра за E + VlogV, Elog_E/V+1V, EloglogC
3. Двусторонняя. Описание алгоритма A^*

1. [15 минут] Алгоритм A^*
1. Доказательство корректности. Необходимое условие.
2. Оценка времени работы, иллюстрация "существует почти прямой путь".


2. [10 минут] Классификация задач поиска пути
1. Невзвешенный граф: bfs, O(E), 1950.
2. Граф без отрицательных рёбер: Дейкстра за O(n²), 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(EV^1/2logN)


3. [15 минут] Алгоритм Флойда
1. Пишем 3 цикла (проверять ли бесконечность)
2. Доказываем корректность подсчёта расстояния (динамика)
3. Восстанавливаем путь (доказательство того, что если нет отрицательных циклов: не циклится, путь простой)
4. Восстанавливаем отрицательный цикл (без док-ва, объяснить, почему)
5. Транзитивное замыкание за O(V³/w)

1. Если осталось время
1. Доказательства 1.5ⁿ для 3-SAT (вернее 2k/(k+1) для k-SAT)


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