| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3839 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | Geothermal | 3569 |
| 7 | cnnfls_csy | 3569 |
| 9 | ecnerwala | 3494 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | maomao90 | 160 |
| 3 | -is-this-fft- | 159 |
| 4 | atcoder_official | 158 |
| 4 | cry | 158 |
| 4 | awoo | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | TheScrasse | 153 |
| 10 | maroonrk | 152 |
Изначально потенциалы равны кратчайшим расстояниям.
Вопрос 1: Как обновлять потенциалы?
Вопрос 2: Как доказывать, что при таком обновлении потенциалов не возникнет ребер отрицательной стоимости?
Говорят, что надо к старым потенциалам надо просто прибавить новое расстояние. Верно ли это?
Верно. Нужно только показать, что при проталкивании потока по минимальному пути не образуется рёбер отрицательного веса (с учетом потенциалов). Далее можно находить кратчайший путь на ребрах с учетом потенциала, подразумевая, что веса ребёр равны w(i,j)+p(j)-p(i), а потенциалы нулевые. Тогда, установив потенциал равным новому кратчайшему расстоянию, получим, что, если изначальный вес ребра равен w(i,j), то потенциал равен p_old + p_new. Вот реализация.
Что такое p_new?
Да, я понимаю, что нужно лишь показать, что не возникает ребер отрицательного веса. Я не могу это доказать.
Спасибо, за реализацию, но мне нужно не это. Мне нужно доказательство. Я не смогу его найти в коде.
Вы написали, что надо установить потенциалы равными новому кратчайшему расстоянию.
Можно по-подробнее, как пересчитывать это расстояние?
На первом шаге вы нашли кратчайшие расстояние от истока до всех вершин и установили потенциал, 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).
Проталкивание потока не добавляет ребер с отрицательной стоимостью. Доказательство можно прочитать тут.
Изначально потенциалы можно поставить и в 0, если нет изначально ребер отрицательной стоимтсти (что чаще всего так и есть).
После каждой итерации к потенциалам прибавляется кратчайшее расстояние (тем самым после первой итерации они естественным образом инициализируются, если были установлены в 0)
Доказать, что не будет отрицательных ребер в новом графе где вес -- это вес + разница потенциалов достаточно легко. Давайте допустим, что отрицательное ребро есть, пусть оно идет из вершины u в вершину v. Тогда
p[u] - p[v] + w[u][v] < 0, а следовательноp[u] + w[u][v] < p[v]. Но это не может быть так, потому что в потенциалах хранятся кратчайщие расстояния до вершин, и верность последнего неравенства означала бы, что кратчайщее расстояное доvможет быть улучшено, но почему-то не было.После каждой итерации к потенциалам добавляются кратчайшие расстояние...
Но это не может быть так, потому что в потенциалах хранятся кратчайщие расстояния до вершин.
Эти две ваши фразы, по моему пониманию, противоречат друг другу.
Насколько я понимаю, вы утверждаете следующее: Перед каждой итерацией (возможно за исключением 0) поиска кратчайшего пути в потенциалах будет храниться кратчайшие расстояния до всех вершин. (Если это действительно так, то здорово! Далее все очевидно).
Как же тогда доказать, что в наших потенциалах окажется кратчайшее расстояние?
Замечу еще кое-что. Допустим мы запустили дейкстру и она у нас нашла кратчайшие расстояния. На следующей итерации у нас будет другой граф! Некоторые ребра добавятся, некоторые удалятся(Добавятся обратные ребра, удалятся насыщенные). Вы это учитываете?
Утверждение: пусть в конце итерации
iмы обновлили потенциалы. Тогда в потенциалах кратчайшие расстояния до вершин в графе по состоянию на начало итерацииi.На нулевой итерации это верно, потому что граф на начало итерации был данным графом, и потенциалы все оказались установлены в кратчайшие расстояния по итогам итерации.
На каждой последующей итерации найденные расстояния уже зависят от потенциалов, и равны
p[0] + shortest[0][i] - p[i], гдеshortest[0][i]-- это кратчайший путь в текущем графе без учета потенциалов (этот факт вытекает из того, как потенциалы вообще влияют на поиск пути). Понятно, что если мы увеличимp[i]на эту величину, новое значение будетp[0] + shortest[0][i], ну аp[0]всегда равен нулю. Значит после обновления потенциалов они опять содержат кратчайшие расстояния для нового графа.Тут важно акцентировать внимание на том, что они содержат кратчайшие расстояния для графа, который БЫЛ на начало итерации, а не того, который стал в новой итерации, которая увидит эти обновленные потенциалы, в то время как мое доказательство опиралось на то, что в потенциалах кратчайшие расстояния для текущей итерации, то есть мое доказательство было неполным.
Чтобы сделать его полным надо рассмотреть два случая:
Ребро
u->vесть в графе на обеих итерациях. Тогда доказательство остается в силеРебро
u->vесть в графе на этой итерации, но его нету на предыдущей. Тогда в графе было было реброv->uс весом-w[u][v], увеличение потока по которому привело к появлению ребраu->v. Но тогдаp[v] - w[u][v] < p[u], и мы могли улучшить расстояние доuна прошлой итерации, но не улучшили.