Блог

Я читал некоторые приложения алгоритма Беллмана-Форда и наткнулся на эту конкретную тему. Из того, что я могу понять из этого, следует, что алгоритму Беллмана-Форда не требуется полное представление сети для правильной работы (поиск кратчайшего пути). Почему это так?

Во-вторых, я хочу спросить, что именно означает «распределенный» Беллман Форд? В частности, как можно было бы разделить массивную сеть, чтобы мы могли использовать упомянутый «распределенный» Беллман Форд.

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

В теме, которую вы упомянули в вопросе, обсуждалось использование алгоритма Беллмана-Форда для поиска наилучшего пути маршрутизации для отправки пакетов данных между маршрутизаторами. В начале каждый маршрутизатор начинается с вектора расстояний до всех непосредственно подключенных сетей. Затем каждый маршрутизатор транслирует свой текущий вектор расстояния на все соседние маршрутизаторы. Затем каждый из соседних маршрутизаторов обновит локальную копию своего вектора расстояния и снова передаст ее своим соседям. Таким образом, каждый из исходных маршрутизаторов сети в конечном итоге обновляет свой собственный вектор расстояния w.r.t. другие маршрутизаторы назначения. Теперь вы можете себе представить, что все маршрутизаторы в конечном счете вычисляют кратчайший путь маршрутизации (полученный из него), не зная всей сети.

Рекомендуемое чтение:

1. Иллюстрация распределенного алгоритма Беллмана-Форда