Беллман-Форд и некоторые факты о графике G?

Мы знаем, что алгоритмы Беллмана-Форда проверяют все ребра на каждом шаге и для каждого ребра, если

d(v)>d(u)+w(u,v)

затем d(v) обновляется таким образом, что w(u,v) — это вес ребра (u, v), а d(u) — длина пути наилучшего поиска для вершины u. если на одном шаге у нас нет обновлений для вершин, алгоритмы завершаются. с учетом этого алгоритма для нахождения всех кратчайших путей из вершины s в графе G с вершиной n после завершения k<n итерации, что из следующего верно?

1) количество ребер во всех кратчайших путях из s не больше k-1

2) вес всех кратчайших путей из s не превосходит k-1

3) Граф не имеет отрицательного цикла.

Я уверен, что одно из них верно, но мой ТА говорит, что два из них верны. Любая идея или намек на эту проблему?


graph math shortest-path graph-theory bellman-ford
person Community    schedule 28.03.2015    source источник
comment
Это кажется слишком широким для переполнения стека; возможно, он лучше подходит для одного из научных сайтов SE?   -  person GoBusto    schedule 28.03.2015
comment
Какие !! тоже доска? нет, я так не думаю. @GoBusto   -  person    schedule 28.03.2015

Ответы (1)


arrow_upward
0
arrow_downward

Давайте пройдемся по утверждениям по одному:

1) количество ребер во всех кратчайших путях из s не больше k-1

Рассмотрим следующий график:

s ---e1---> n1 ---e2---> n2 ---e3---> n3

Если ребра упорядочены как задано (e1, e2, e3), то у вас будет правильное расстояние для каждого узла после первой итерации (проверка e1 обновляет n1, затем проверка e2 обновляет n2 и так далее). Итак, в этом случае алгоритм останавливается после k=2 итераций, потому что вторая итерация ничего не меняет. Количество ребер в самом длинном кратчайшем пути равно 3, а 3 <= 2-1 не выполняется. Следовательно, это утверждение неверно. Однако если все ребра оцениваются одновременно, то утверждение верно (каждая итерация может пройти только на одно ребро дальше, чем предыдущая итерация).

2) вес всех кратчайших путей из s не больше k-1

Ни количество ребер, ни их общий вес не ограничены k-1. Учтите, что все ребра в приведенном выше примере имеют вес 1000. Очевидно, что связи с k нет.

3) Граф не имеет отрицательного цикла.

Если вы определяете алгоритм так, как вы это сделали (заканчивается, когда не вносятся изменения), то это правильно. Любой отрицательный цикл вызовет бесконечный цикл, потому что расстояния вершин в этом цикле последовательно уменьшаются.

person Nico Schertler    schedule 28.03.2015
comment
В бланке ответов указано, что два предложения верны. что вы подразумеваете под тем, что все ребра оцениваются одновременно, тогда утверждение верно - person ; 28.03.2015
comment
Например. проверки выполняются параллельно в режиме SIMD. Или делается копия старого состояния и по этой копии выполняются проверки (что было бы пустой тратой времени и памяти). Бланки ответов не обязательно верны. - person Nico Schertler; 28.03.2015
comment
можно ли более подробно обо всех ребрах оцениваются одновременно? не могли бы вы добавить пример для пояснения? - person ; 28.03.2015
comment
Это просто означает модификацию алгоритма, которая распараллеливает внутренний цикл. Это не может быть сделано тривиально на обычном процессоре и не имеет значения для кода, который вы связали (стр. 12). Кроме того, в коде нет условия, что алгоритм завершает работу при отсутствии изменений (но после постоянного числа итераций). Это модификация задачи? - person Nico Schertler; 28.03.2015
comment
Я нашел это в Google. благодаря. да этот алгоритм запускает постоянное число и не когда не меняется.... да, вы правы. но мое недоразумение заключается в том, почему у нас есть параллелизм (1). - person ; 28.03.2015
comment
Если ребро e2 проверяется во время одной итерации распараллеленной версии, оно не может получить доступ к результатам проверки для e1 в той же итерации (поскольку проверка для e1 все еще выполняется). И эта зависимость в рамках одной итерации является причиной того, что (1) не выполняется. - person Nico Schertler; 28.03.2015
comment
ничего себе, вы имеете в виду, если мы используем параллельную версию, (1) правильно, если мы не использовали, если это ложь? - person ; 28.03.2015
comment
Зависит от метода распараллеливания. Но да, это может стать правдой. - person Nico Schertler; 28.03.2015
comment
так вообще без какой-то распараллеленной версии это ложь? +1. - person ; 28.03.2015
comment
Итак, извините, если на каждом шаге мы будем проверять одно ребро, то (1) верно? да? - person ; 28.03.2015
comment
не могли бы вы привести пример для одновременной проверки? - person ; 09.04.2015