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