Какая версия алгоритма Беллмана-Форда верна, CLRS или Алгоритмы?

Question

Код ниже взят из Введение в алгоритмы, 3-е издание .

BELLMAN-FORD(G,w,s)
1 INITIALIZE-SINGLE-SOURCE(G,s)
2 for i = 1 to |G.V|-1
3   for each edge (u,v) ∈ G.E
4       RELAX(u,v,w)
5 for each edge (u,v) ∈ G.E
6    if v.d > u.d + w(u,v)
7       return FALSE
8 return TRUE

Ниже следует из Алгоритмы, 4-е издание .

for (int pass = 0; pass < G.V(); pass++)
   for (int v = 0; v < G.V(); v++)
      for (DirectedEdge e : G.adj(v))
          relax(e);

Кажется, единственное отличие - это количество проходов.

for i = 1 to |G.V|-1

и

for (int pass = 0; pass < G.V(); pass++)

Какой из них прав?

Answer 1

Кратчайший путь к любой вершине графа имеет не более | V | -1 ребер и достигает не более | V | -1 вершин, отличных от источника.

После того, как Nth пройдет через все ребра, вершина Nth , достигнутая по любому кратчайшему пути, гарантированно получит правильную назначенную стоимость, поэтому алгоритм требует только | V | -1 передает для учета всех кратчайших путей.

Answer 2

РЕДАКТИРОВАТЬ: вопрос был на самом деле о количестве проходов во внешнем цикле: N-1 или статья Н. Беллмана, связанная ниже: «Метод функционального уравнения динамического программирования в сочетании с приближением в пространстве политик дает итерационный алгоритм, который сходится не более чем за (N - 1) итераций. " Обоснование дано в CLRS в Лемма 24.2 и ее доказательство .

ОРИГИНАЛЬНЫЙ ОТВЕТ:

for each edge (u,v) ∈ G.E

и

for (int v = 0; v < G.V(); v++)
  for (DirectedEdge e : G.adj(v))

эквивалентны для целей этого алгоритма: они оба повторяются по каждому ребру графа. Вторая версия просто перебирает все вершины первой, а для каждой вершины перебирает свои инцидентные ребра.

Что касается строк 5-7 CLRS, они проверяют отсутствие цикла отрицательного веса, но это, очевидно, игнорируется в выписке, которую вы опубликовали из Алгоритмы, 4-е издание . Проверка Оригинальная статья Беллмана Я не вижу этой последней проверки, так что это может быть добавление CLRS или другого.