Min Cost Потоки (СПБГУ МатМех, весна 2013, спецкурс 344-й группы)

  1. Ford Bellman
    1. Задача: найти все кратчайшие пути из s в t
    2. Решение: d[k, v] = min(d[k-1, u] + w[u, v])
    3. Время работы O(VE), памяти O(V) (храним только последний слой)
    4. Реализация с break. Реализация с очередью.
    5. Поиск отрицательного цикла за O(VE).
  2. min cost потоки
    1. Поточная сеть с весами (w, -w, случай ориентированного и неориентированного графа)
    2. Задача: ищем поток размера k минимального веса. Обратное ребро имеет вес (-w).
    3. Алгоритм поиска mincost потока размера k, используя алгоритм Форда-Белмана за O(k*VE)
    4. Док-во корректности: рассмотрим разность mincost потока размера (k+1) и mincost потока размера (k).
    5. База: отсутвие циклов отрицательного веса. Если такие циклы есть, нужно сперва найти циркуляцию минимального веса.
  3. min cost потоки и отрицательные циклы
    1. Как строить min cost поток, если есть отрицательные циклы?
    2. Как искать цикл минимального среднего веса за O(VElogMax)?
    3. Полиномиальный алгоритм нахождения min cost потока (без док-ва)
  4. Применения min cost потоков
    1. Задача о назначениях, минимизировать сумму
    2. Задача о назначениях, минимизировать максимум
    3. Транспортная задача
    4. Распределения задач (отрезки) по k одинаковым автоматам. Нужно максимизировать стоимость выполненных заданий.
    5. Not read Покрыть граф циклами минимальной суммарной стоимости.
    6. Дан план, решающий транспортную задачу. Нужно его улучшить, или сказать, что он оптимален.
    7. В неориентированном графе найти простой цикл минимальной длины (веса), проходящий через две данные вершины.
  5. Дейкстра с потенциалами
    1. Потенциалы: изменяем веса ребер, кратчайшие пути остатся кратчайшими
    2. pv := dv → все новые веса ≥ 0
    3. Применение к потокам
      1. Eсли изначально есть отрицательные ребра, пустили ford-bellman-а, pv := dv, иначе pv := 0
      2. Дополняющий путь ищем Дейкстрой. После этого делаем pv += dv.