Использование алгоритма Беллмана-Форда: как правильно обходить каждое ребро?

Question

Я делаю домашнее задание, где мне нужно запустить алгоритм Беллмана-Форда, начиная с вершины z.Он хочет, чтобы я «На каждом проходе ослаблял ребра в том же порядке, что и на рисунке, и показывал значения d и pi после каждого прохода».Из того, что я понимаю, я думал, что этот алгоритм пересекает график как BFS, что имеет смысл на рисунке, который они хотят, чтобы я использовал, поэтому я не могу понять, как будет работать тот же путь.Если бы кто-нибудь мог указать мне правильное направление, указав, как начать, это было бы очень полезно.Вопрос и цифра, к которой относится вопрос:

Answer 1

Я постараюсь указать на вашу ошибку.

Я думал, что этот алгоритм пересекает график как BFS

Это не правда. Этот алгоритм многократно повторяет все ребра графа и «расслабляет» их до тех пор, пока он не достигнет стабильного состояния (когда больше не может быть выполнено расслабление)

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

Итак, чтобы ответить на ваш вопрос, выберите любой порядок по краям и начните так называемое «расслабление» их. Для каждого ребра установите его значение d указывающего узла равным кратчайшему расстоянию от Z, и задайте его pi как узел-предшественник. повторяйте это, пока все значения не станут стабильными.

Надеюсь, что ответит на ваш вопрос.

Answer 2

Как сказал Ido.Co, в Bellman Ford нет определенного порядка сканирования / итерации. Но говорят, что сканирование в первую очередь, выполнение быстрее.