Простой обход графа с использованием алгоритма беллмана-форда

Я немного застрял проблема, в которой мы должны заполнить значения после запуска двух итераций алгоритма Беллмана-Форда на базовом ориентированном графе.

Мне кажется, что я понимаю первую итерацию и понимаю концепцию «ослабления весов ребер», поскольку обнаруживаются более короткие пути. Однако я не понимаю, как вторая итерация в этой конкретной проблеме привела бы к каким-либо более коротким путям, чем те, которые находятся в первой итерации.

Например, я знаю, что посещение узла «C» через путь, начинающееся с узла A, затем переход к узлу «B», а затем переход к узлу «C» будет иметь общую «стоимость» 6 + 8 = 14. Однако, поскольку порядок обхода этого графа: AB, AC, BC, BD и т. д., стоимость достижения узла C через узел B (14) никогда не будет сохранена, потому что более короткий путь к C непосредственно из A уже был бы найден (что дает стоимость 7) Я не понимаю, как какие-либо дополнительные итерации могут дать более короткий путь, например, от A до C, что, по-видимому, имеет значение для последующих итераций.

Bellman-Ford algorithm homework problem

Может этот вопрос должен быть в cs.stackexchange.com

rvazquezglez 13.02.2019 00:19
2
1
103
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

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

Другие вопросы по теме