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

Question

Пожалуйста, обратитесь к следующей странице для алгоритма Беллмана Форда (он показывает, например). 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].

Answer 1

Эта проблема волшебным образом исчезает, если вы используете слегка другую версию 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

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