Алгоритм Беллмана-Форда - Почему ребра могут быть обновлены не по порядку?

Алгоритм Беллмана-Форда определяет кратчайший путь от источника до всех других вершин. Первоначально расстояние между и всеми остальными вершинами установлено в . Затем вычисляется кратчайший путь от до каждой вершины; это продолжается для итераций. Мои вопросы: $s$ $s$ $\infty$ $s$ $|V|-1$

Почему должны быть итерации ? $|V|-1$
Было бы важно, если бы я проверил края в другом порядке?
Скажем, если я сначала проверю ребра 1,2,3, но затем на второй итерации я проверю 2,3,1.

Профессор MIT Эрик сказал, что порядок не имеет значения, но меня это смущает: не будет ли алгоритм некорректно обновлять узел на основе ребра если его значение зависит от ребра но обновляется после ? $x_2$ $x_1$ $x_1$ $x_2$

algorithms shortest-path user1675999
источник

Какую реализацию вы считаете? У динамического программирования нет проблем с порядком, очевидно; для других это может быть нетривиально.

Рафаэль

Ответы:

Рассмотрим кратчайший путь из в , . Этот путь состоит не более чем из ребро, потому что повторение вершины в кратчайшем пути всегда плохая идея (или, по крайней мере, существует кратчайший путь, который не повторяет вершины), если у нас нет циклов с отрицательным весом. $s$ $t$ $s, v_1, v_2, \dots, v_k, t$ $|V|-1$

В первом раунде мы знаем, что ребро будет ослаблено, поэтому оценка расстояния для будет правильной после этого раунда. Обратите внимание, что мы понятия не имеем, что такое в этой точке, но, поскольку мы ослабили все ребра, мы, должно быть, ослабили и это. Во втором раунде мы расслабляемся в некоторой точке. Мы до сих пор не знаем, что такое или , но мы знаем, что их оценки расстояний верны. $(s, v_1)$ $v_1$ $v_1$ $(v_1, v_2)$ $v_1$ $v_2$

Повторяя это, после некоторого раунда мы ослабили , после чего оценка расстояния для является правильной. Мы не знаем, что такое , пока весь алгоритм не закончится, но мы знаем, что это произойдет в какой-то момент (при условии отсутствия циклов с отрицательным весом). $k+1$ $(v_k, t)$ $t$ $k$

Таким образом, важно наблюдение , что после первого раунда , то -й узел кратчайшего пути должен иметь свою оценку расстояния установлен на правильное значение. Как путь не более ребро длинное, раунда достаточно, чтобы найти этот кратчайший путь. Если Третий раунд все еще что-то меняет, затем происходит что-то странное: все пути уже должны быть «согласованы» с их окончательными значениями, поэтому мы должны иметь ситуацию, что существует некоторый отрицательный цикл веса. $i$ $i$ $|V|-1$ $|V|-1$ $|V|$

Алекс тен Бринк
источник

У меня есть небольшое сомнение. Я считаю, что | v | -1 - наихудшее число раундов, после которого вычисляется кратчайший путь от s до t. Предположим, у нас есть вершины s, v1, v2..vn, t. Если рёбра выбираются в таком порядке, скажем, (s, v1), (v1, v2) .. (vn, t), что за одну итерацию мы получим кратчайший путь от s до t. Это просто для понимания и На практике мы не знаем порядок выбора ребер и, следовательно, | v | -1 раундов. Я прав?

Whokares

@whokares: да, вам может повезти и вы найдете кратчайший путь в первом раунде. До последнего раунда вы точно не знаете, что найденное вами значение действительно является кратчайшим путем, но это может быть так. Алгоритм Дейкстры, по сути, «вызывает» это: если все ребра имеют неотрицательные веса, то очередь приоритетов, используемая в алгоритме Дейкстры, «предсказывает» порядок, в котором вы должны ослаблять ребра, чтобы вы нашли все кратчайшие пути в вашем первом раунде релаксаций.

Алекс тен Бринк

Спасибо за обновление. Я получил его. В одном из материалов он упоминается как <br> Слайд 6: Неправильный выбор порядка релаксации может привести к экспоненциальному множеству релаксаций: <br> Слайд 8: «Умный» порядок релаксации краев <br>

whokares

Независимо от порядка ребер в каждой итерации, кратчайшие пути будут вычисляться в | v | -1 итерациях, верно? Почему он говорит экспоненциально. Имеет ли он в виду, что если мы выбрали один и тот же порядок для всех итераций, которые мы обычно делаем, будет вызван код релаксации, но обновление метки для вершины может произойти только меньшее количество раз из-за порядка, тем самым сохраняя процессор время?

Whokares

@whokares: первый алгоритм, который они представляют (который может иметь экспоненциальное время выполнения), не ослабляет все ребра в цикле, а вместо этого находит какое-то ребро, для которого операция релаксации что-то изменит, и ослабляет это ребро. Если вы продолжаете делать это, и нет отрицательного цикла веса, то в конечном итоге никакие ребра вам больше не помогут, и вы остановитесь. Однако из-за того, что у вас нет раундов и нет определенного порядка, по которому можно расслабиться, вы можете сделать экспоненциальное количество расслаблений. Усовершенствованный алгоритм, который они представляют, - это Bellman-Ford, у которого есть раунды.

Алекс тен Бринк

Самая длинная дорожка может быть без всяких циклов |V|. Мы начнем с источника, поэтому у нас уже есть путь длиной 1, поэтому нам нужно |V| - 1больше узлов, чтобы получить самый длинный путь.

Порядок не имеет значения, потому что каждый заказ будет поддерживать инвариант: после nитераций значение для каждого узла будет меньше или равно стоимости минимальной стоимости пути от sузла, содержащего не более nребер.

Если в начале итерации стоимость верна до nузлов, то в конце итерации она верна до n+1узлов. Изменение порядка может привести к тому, что некоторые узлы будут стоить дешевле, прежде чем они будут обычно обновляться, но в конечном итоге они все равно будут обновлены.

ФГБ
источник

Я не знаю, только ли это я, или я не могу действительно визуализировать эти факты легко. Мне все еще кажется, что могут быть некоторые узлы, которые не обновляются в итерациях V-1.

user1675999

Нет, у вас есть | E | = | V | -1 ребра, когда у вас есть | V | узлы соединены простым путем без циклов. И у вас есть | V | -1 итераций, удалите свой ответ, потому что это неправильно.

Сэм

@sam Кто ты и что ты имеешь в виду при ответе?

ФГБ