Кратчайшие расстояния в графах

  1. Алгоритм Флойда
    1. Пишем 3 цикла (проверять ли бесконечность)
    2. Доказываем корректность подсчёта расстояния (динамика)
    3. Восстанавливаем путь (доказательство того, что если нет отрицательных циклов: не циклится, путь простой)
    4. Восстанавливаем отрицательный цикл (без док-ва, объяснить, почему)
    5. Транзитивное замыкание за O(V3/w)
  2. Алгоритм Форда-Беллмана
    1. Реализация за O(VE) c 2D массивом
    2. Реализация за O(VE) c 1D массивом
    3. Доказательство динамикой
    4. Реализация за O(kE) (c break)
    5. Реализация с очередью, работающая в худшем случае за O(VE)
    6. Алгоритмы с добавлением в начало, Левита. Попытка написать Дейкстру для графов с отрицательными весами.
--- Перерыв ---
  1. Поиск цикла отрицательного веса Форд-Беллманом
    1. Алгоритм за O(VE), проверяющий наличие
    2. Восстановление цикла за O(V)
    3. Доказательство корректности восстановления (3 леммы)
  2. Поиск цикла минимального среднего веса.
    1. Алгоритм бинпоиском.
    2. Оценка точности бинпоиска 1/n2
    3. Алгоритм Карпа за O(VE)
    4. [не успеем] Доказательство алгоритма Карпа