Расстояние в графах (11 ноября 2016, Лёша)

  1. Поиск в ширину (bfs): поиск расстояния от одной вершины до всех в невзвешенном графе
    1. Вариант на двух очередях (вершины расстояния D, вершины расстояния D+1)
    2. Вариант на одной очереди
    3. Восстановление пути

  2. Дейкстра: поиск расстояния от одной вершины до всех во взвешенном графе с неотрицательными весами
    1. Описание алгоритма
    2. Вариант реализации за Θ(n2 + m) (в лоб)
    3. Вариант реализации за Θ((n + m) log n) (с кучей)
    4. Восстановление пути

  3. Флойд: поиск расстояния между всеми парами вершин во взвешенном графе с произвольными весами, без отрицательных циклов
    1. Реализация за Θ(n3)
    2. Обоснование корректности (динамика с инвариантом "учтены все пути из i в j, проходящие через вершины 1..k")
    3. Восстановление пути
  4. [skipped] (можно выкинуть, особо не нужно) Поиск отрицательного цикла Флойдом

Расстояние в графах (18 ноября 2016, Паша)

  1. Форд-Беллман: поиск расстояния от одной вершины до всех во взвешенном графе с произвольными весами, без отрицательных циклов
    1. Реализация за O(nm)
    2. Реализация с очередью, O(n) памяти и O(m) времени в среднем (не путать с алгоритмом Левита!)

  2. Поиск отрицательного цикла Форд-Беллманом
    1. Алгоритм за O(nm)
    2. Доказательство корректности
      1. Lm #1: В каждый момент времени d[v] ≥ d[e[v].begin] + e[v].weight
      2. Lm #2: Ссылки циклятся
      3. Lm #3: Любой цикл на ссылках имеет отрицательный вес

  3. Потенциалы, алгоритм Джонсона: поиск расстояния между всеми парами вершин во взвешенном графе с произвольными весами
    1. Идея потенциалов
    2. Алгоритм за O(nmlogn)

  4. (займёт минут 5) Анонс возможных улучшений
    1. Фибоначчиева куча даёт Дейкстре O(m + nlogn), Джонсону O(nm + n2logn)
    2. Алгоритм Гольдберга ищет потенциалы быстрее Форд-Беллмана: за O(m√ n logN)
    3. В неориентированном графе с неотрицательными весами умеют искать кратчайший путь между двумя выделенными вершинами за O(n + m)