Алгоритм кратчайшего пути Беллмана-Форда

В этом видео объясняется алгоритм Беллмана-Форда для поиска кратчайшего пути от одного узла до всех остальных узлов.

Сначала он создаёт таблицу, в которой хранятся все узлы, а также стоимость кратчайшего пути до этого узла и его предыдущего элемента в порядке.

Алгоритм начинается с инициализации расстояний до всех узлов бесконечностью, за исключением начального узла, который равен нулю. Затем он итеративно ослабляет все рёбра графа, выполняя в общей сложности V - 1 раз, где V — количество узлов. На каждой итерации алгоритм проверяет каждое ребро и обновляет кратчайшее расстояние до конечного узла, если найден более короткий путь. Процесс продолжается до тех пор, пока все рёбра не будут проверены на наличие возможных обновлений. После V - 1 итераций алгоритм проверяет наличие циклов с отрицательным весом в графе. Если таких циклов не обнаружено, кратчайшее расстояние от начального узла до любого другого узла можно найти, обратившись к таблице.

Ссылка на код на GitHub: https://github.com/ByteQuest0/Impleme...

Прежде чем изучать этот алгоритм, рекомендуется изучить основы графов, такие как узлы, рёбра, веса, способы их представления и т. д.

На этом канале также есть похожие анимированные алгоритмы и видео о структурах данных, которые могут быть вам полезны:

Алгоритм Кнута-Морриса-Пратта:    • Knuth-Morris-Pratt Algorithm  

Алгоритм поиска в глубину:    • Depth First Search Visually Explained | DF...  

Введение в графы:    • Graphs Explained Visually | Data Structures  

Двоичные деревья поиска:    • Binary Search Tree Visually Explained | Fu...  

Связанные списки:    • Linked Lists Explained Visually  

Использованные инструменты: Manim (библиотека анимации Python от 3blue1brown) и Adobe Premier Pro для монтажа видео.

Музыка, использованная в качестве фона:

Sovereign, автор: Кевин Маклеод | https://incompetech.com/
Музыка предоставлена ​​https://www.chosic.com/free-music/all/
Creative Commons CC BY 3.0
https://creativecommons.org/licenses/...