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

    Если в каких-то задачах граф взвешенный, то веса неотрицательные.

  1. Упражнения-напоминания
    1. За O(n + m) найти в незвешенном неорграфе цикл нечетной длины.
    2. Кратчайший цикл в графе, проходящий через данное ребро за O(E)

  2. Задачи
    1. bfs на графе с весами из {0, 1} (вместо очереди дек)
    2. bfs на графе с весами из {1, 2} (три очереди)
    3. В неориентированном графе за O(VE) найти две вершины на максимальном расстоянии друг от друга.
    4. Дан взвешенный неограф. Найти путь из s в t такой, что максимальное ребро минимально.
    5. Дан взвешенный неограф. Найти путь из s в t такой, что сумма двух максимальных ребер на пути минимальна. А если орграф?
    6. Дан взвешенный неограф. Найти все рёбра, лежащие на кратчайших путях из s в t.
    7. Дан взвешенный орграф. Найти кратчайший путь, проходящий по всем k ≤ 10 выделенным вершинам.
    8. Ацикличный граф: матрица достижимости за O(VE/w) (w − размер машинного слова)
    9. Произвольный граф: матрица достижимости за O(V3/w) (оптимизируем Флойда)

  3. [skipped] Дополнительные задачи
    1. [skipped] Кратчайший цикл в графе за O(E2), за O(VE)
    2. [skipped] Дана бесконечная прямая дорога ширины W. На дороге есть точечные препятствия в точках xi, yi.
      Круглую машину какого максимального радиуса мы сможем провести с -∞ до +∞?
    3. [skipped] Дан взвешенный неограф. Найти длину кратчайшего среди путей из s в t, проходящих хотя бы по одной вершине не из множества A.