АЛГОРИТМ БЕЛЛМАНА ФОРДА PYTHON

Алгоритм Беллмана-Форда – это алгоритм поиска кратчайшего пути во взвешенном графе, который может работать с отрицательными весами ребер. Он оценивает расстояние от начальной вершины до всех остальных вершин в графе. Рассмотрим пример кода на Python:

def Bellman_Ford(graph, start):    distance = {}    predecessor = {}    for node in graph:        distance[node] = float('inf') # Устанавливаем бесконечное расстояние        predecessor[node] = None    distance[start] = 0    for _ in range(len(graph) - 1):        for node in graph:            for neighbor in graph[node]:                new_distance = distance[node] + graph[node][neighbor] # Расстояние до соседней вершины                if new_distance < distance[neighbor]:                    distance[neighbor] = new_distance                    predecessor[neighbor] = node    return distance, predecessor

На вход функции передается словарь-граф и начальная вершина. Функция возвращает два словаря: расстояние и предшественник каждой вершины.

Алгоритм Беллмана-Форда имеет сложность O(V * E), где V - количество вершин в графе, а E - количество ребер в графе. При работе с большими графами необходимо учитывать данную особенность алгоритма.