Алгоритмы и структуры данных. Лекция 9. Алгоритм Форда-Беллмана (Bellman-Ford algorithm) на Python

• Алгоритм используется для поиска кратчайшего пути между вершинами взвешенного графа.  

• Применяется к графам с ребрами с отрицательным весом.  

• Может не находить кратчайшие пути при наличии отрицательных циклов.  

• Алгоритм состоит из нескольких фаз, напоминающих алгоритм Декстера.  

• На каждой фазе осуществляется обход всех вершин графа.  

• Релаксация улучшает значение текущего пути до вершины, сравнивая его с текущим путем плюс вес ребра.  

• Используется словарь для хранения информации о путях.  

• Ключ словаря - вершина графа, значение - структура с полями стоимость пути и указатель на вершину.  

• Значение пути начальной вершины равно нулю, остальных - бесконечности.  

• Алгоритм принимает на вход граф, стартовую вершину и конечную вершину.  

• Инициализирует все узлы бесконечностью и записывает словарь.  

• Обход графа проверяет, есть ли смысл заменять стоимость пути.  

• Проверяется наличие отрицательных циклов.  

• Если найден отрицательный цикл, решения нет.  

• Восстановление пути осуществляется аналогично алгоритму Декстера.  

• Граф инициализируется и запрашивается стоимость пути от одной вершины до другой.  

• Пример расчета стоимости пути от А до Е.  

• Временная сложность алгоритма: в худшем и среднем случае O E^2, в лучшем случае линейно зависит от количества ребер.