Блог пользователя skrydg

Дейкстра с потенциалами(mincost maxflow)
Автор skrydg, история, 9 лет назад, По-русски

Изначально потенциалы равны кратчайшим расстояниям.

Вопрос 1: Как обновлять потенциалы?

Вопрос 2: Как доказывать, что при таком обновлении потенциалов не возникнет ребер отрицательной стоимости?

Говорят, что надо к старым потенциалам надо просто прибавить новое расстояние. Верно ли это?

  • Проголосовать: нравится
  • +21
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Верно. Нужно только показать, что при проталкивании потока по минимальному пути не образуется рёбер отрицательного веса (с учетом потенциалов). Далее можно находить кратчайший путь на ребрах с учетом потенциала, подразумевая, что веса ребёр равны w(i,j)+p(j)-p(i), а потенциалы нулевые. Тогда, установив потенциал равным новому кратчайшему расстоянию, получим, что, если изначальный вес ребра равен w(i,j), то потенциал равен p_old + p_new. Вот реализация.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Что такое p_new?

    Да, я понимаю, что нужно лишь показать, что не возникает ребер отрицательного веса. Я не могу это доказать.

    Спасибо, за реализацию, но мне нужно не это. Мне нужно доказательство. Я не смогу его найти в коде.

    → Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Вы написали, что надо установить потенциалы равными новому кратчайшему расстоянию.

    Можно по-подробнее, как пересчитывать это расстояние?

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      На первом шаге вы нашли кратчайшие расстояние от истока до всех вершин и установили потенциал, p[i] = расстояние от истока до i. Теперь вы можете рассматривать веса ребёр равными w(i,j) + p(j) — p(i), а потенциал равным нулю. На новом шаге вы находите кратчайшие пути из истока до каждой вершины, добавляете обратные ребра и изменяете потенциал в соответствии с новыми кратчайшими расстояниями. Итак, в графе с весами ребёр, равными w(i,j) + p(j) — p(i) вы нашли новые кратчайшие расстояния и собираетесь изменить потенциал. Пусть новый потенциал равен p'. Веса ребёр теперь станут равными w(i,j) + p(j) — p(i) + p'(j) — p'(i) = w(i,j) + (p(j) + p'(j)) — (p(i) + p'(i)), то есть в исходном графе потенциалы вершин стали равными p(i) + p'(i).

      Проталкивание потока не добавляет ребер с отрицательной стоимостью. Доказательство можно прочитать тут.

      → Ответить
»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Изначально потенциалы можно поставить и в 0, если нет изначально ребер отрицательной стоимтсти (что чаще всего так и есть).

После каждой итерации к потенциалам прибавляется кратчайшее расстояние (тем самым после первой итерации они естественным образом инициализируются, если были установлены в 0)

Доказать, что не будет отрицательных ребер в новом графе где вес -- это вес + разница потенциалов достаточно легко. Давайте допустим, что отрицательное ребро есть, пусть оно идет из вершины u в вершину v. Тогда p[u] - p[v] + w[u][v] < 0, а следовательно p[u] + w[u][v] < p[v]. Но это не может быть так, потому что в потенциалах хранятся кратчайщие расстояния до вершин, и верность последнего неравенства означала бы, что кратчайщее расстояное до v может быть улучшено, но почему-то не было.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    После каждой итерации к потенциалам добавляются кратчайшие расстояние...

    Но это не может быть так, потому что в потенциалах хранятся кратчайщие расстояния до вершин.

    Эти две ваши фразы, по моему пониманию, противоречат друг другу.

    Насколько я понимаю, вы утверждаете следующее: Перед каждой итерацией (возможно за исключением 0) поиска кратчайшего пути в потенциалах будет храниться кратчайшие расстояния до всех вершин. (Если это действительно так, то здорово! Далее все очевидно).

    Как же тогда доказать, что в наших потенциалах окажется кратчайшее расстояние?

    Замечу еще кое-что. Допустим мы запустили дейкстру и она у нас нашла кратчайшие расстояния. На следующей итерации у нас будет другой граф! Некоторые ребра добавятся, некоторые удалятся(Добавятся обратные ребра, удалятся насыщенные). Вы это учитываете?

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Утверждение: пусть в конце итерации i мы обновлили потенциалы. Тогда в потенциалах кратчайшие расстояния до вершин в графе по состоянию на начало итерации i.

      На нулевой итерации это верно, потому что граф на начало итерации был данным графом, и потенциалы все оказались установлены в кратчайшие расстояния по итогам итерации.

      На каждой последующей итерации найденные расстояния уже зависят от потенциалов, и равны p[0] + shortest[0][i] - p[i], где shortest[0][i] -- это кратчайший путь в текущем графе без учета потенциалов (этот факт вытекает из того, как потенциалы вообще влияют на поиск пути). Понятно, что если мы увеличим p[i] на эту величину, новое значение будет p[0] + shortest[0][i], ну а p[0] всегда равен нулю. Значит после обновления потенциалов они опять содержат кратчайшие расстояния для нового графа.

      Тут важно акцентировать внимание на том, что они содержат кратчайшие расстояния для графа, который БЫЛ на начало итерации, а не того, который стал в новой итерации, которая увидит эти обновленные потенциалы, в то время как мое доказательство опиралось на то, что в потенциалах кратчайшие расстояния для текущей итерации, то есть мое доказательство было неполным.

      Чтобы сделать его полным надо рассмотреть два случая:

      1. Ребро u->v есть в графе на обеих итерациях. Тогда доказательство остается в силе

      2. Ребро u->v есть в графе на этой итерации, но его нету на предыдущей. Тогда в графе было было ребро v->u с весом -w[u][v], увеличение потока по которому привело к появлению ребра u->v. Но тогдаp[v] - w[u][v] < p[u], и мы могли улучшить расстояние до u на прошлой итерации, но не улучшили.

      → Ответить