Почему нельзя ослабить все ребра в первой итерации алгоритма Беллмана Форда?

Пожалуйста, обратитесь к следующей странице для алгоритма Беллмана Форда (он показывает, например). http://compprog.wordpress.com/2007/11/29/one-source-shortest-path-the-bellman-ford-algorithm

Я все еще не понимаю. В первой итерации внешнего цикла, например, вы сначала изменяете ребро 1-> 2 и ребро 1-> 4, в чем проблема с ослаблением ребра 2-> 3, 2-> 5, 4- >3, 4->5, на том же шаге, так как у нас есть d[2] и d[4].


algorithm bellman-ford graph-algorithm
person shahalpk    schedule 21.11.2011    source источник
comment
Нет проблем. Вы можете это сделать, и на самом деле код, который вы связали, делает это (или может, в зависимости от порядка, в котором ребра появляются во входном файле). Вы только что выбрали определенный порядок ослабления краев, который приводит к хорошему результату. В связанном посте все ребра проверяются каждый раз на этапе релаксации, а расстояния обновляются по мере релаксации каждого ребра, поэтому для конкретного графа вполне возможно, что все ребра будут полностью релаксированы в конце первой итерации релаксации.   -  person Erick G. Hagstrom    schedule 10.11.2015

Ответы (1)


arrow_upward
1
arrow_downward

Эта проблема волшебным образом исчезает, если вы используете немного другую версию Bellman-Ford:

set toRelax = {initial_vertex}
while toRelax is not empty:
    u = remove a vertex from toRelax
    for each neighbour v of u:
       if we can relax u-v:
          relax u-v
          add v to toRelax

Обратите внимание, что каждый «шаг» теперь включает одну вершину! Вещи, выполняемые на «одном шаге» или нет, являются просто артефактом конкретной реализации, которую вы используете, и в конечном итоге не меняют алгоритм.

person hugomg    schedule 21.11.2011
comment
Мне очень нравится эта версия. Вы только пытаетесь ослабить ребра, которые могут изменить текущее состояние. Есть ли что-нибудь в литературе об этом подходе? Это действительно все еще B-F? Это похоже на итеративный метод Дейкстры, когда вместо оптимизации вершины за один шаг вы просто получаете ее настолько хорошо, насколько это возможно на этом шаге, сохраняя при этом право вернуться к ней в будущем. - person Erick G. Hagstrom; 10.11.2015
comment
Но кажется, что этот подход теряет способность обнаруживать отрицательные циклы. stackoverflow.com/questions/29817131/ - person Erick G. Hagstrom; 10.11.2015